993 research outputs found
Erratum: A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints
No full textIn the article, “A Tabu Search Heuristic for the Vehicle Routing Problem with Two-Dimensional Loading Constraints” by M. Gendreau et al., which appeared in the January issue of Networks (Networks 51 (2008), 4–18), the last author’s name was misspelled
Simulation-based optimization of agent scheduling in multiskill call centers.
No full textWe examine and compare simulation-based algorithms for solvingthe agent scheduling problem in a multiskill call center.This problem consists in minimizing the total costs of agents underconstraints on the expected service level per call type,per period, and aggregated.We propose a solution approach that combines simulation withinteger or linear programming, with cut generation.In our numerical experiments with realistic problem instances,this approach performs better than all other methods proposedpreviously for this problem.We also show that the two-step approach, which is the standard methodfor solving this problem, sometimes yield solutions that arehighly suboptimal and inferior to those obtained by our proposed method.<br/
Gendreau et al. (2006) data set
No full textGendreau et al.’s (2006) benchmark instances consist of 27 problem instances, with the number of customers varying between 15 and 100. The nodes’ coordinates, the weights demanded by the customers, and the vehicle weight capacities were taken from the CVRP instances of Toth and Vigo (2002). The loading space was defined as W = 25, H = 30, and L = 60. The loading space of the vehicles and widths, lengths, and heights of requested items were generated by Gendreau et al. (2006)
The Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints and Unitary Demands: A Branch-and-Price Approach
No full textIn this work we study a suppliers selection and routing problem where a fleet of
homogeneous vehicles with a predefined capacity is available for procuring different products from
different suppliers with the aim to minimize both the traveling and the purchasing costs. Decisions are
further complicated by the presence of pairwise incompatibility constraints among products, implying
the impossibility of loading two incompatible products on the same vehicle. The problemis known as
the Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints.We study a
variant in which products demand is unitary and propose a column generation approach based on a
Dantzig-Wolfe reformulation of the problem, where each column represents a feasible vehicle route
associated with a compatible purchasing plan.Two different procedures are introduced to solve the
pricing problem, namely a labeling algorithm solving a Resource-Constrained Elementary Shortest
Path Problem on an expanded graph, and a tailored branch-and-cut algorithm. Due to the integrality
request on variables, we embed the column generation in a branch-and-bound framework and propose
different branching rules, thus obtaining a branch-and-price procedure. Extensive tests, carried out on
a large set of instances, show that our branch-and-price method performs well, improving on average,
both in quality and in computational time, solutions obtained by a branch-and-cut approach existing in
the literature that relies on a three-index connectivity constraints based formulation
The Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints and Unitary Demands: A Branch-and-Price Approach
No full textIn this work we study a suppliers selection and routing problem where a fleet of
homogeneous vehicles with a predefined capacity is available for procuring different products from
different suppliers with the aim to minimize both the traveling and the purchasing costs. Decisions are
further complicated by the presence of pairwise incompatibility constraints among products, implying
the impossibility of loading two incompatible products on the same vehicle. The problemis known as
the Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints.We study a
variant in which products demand is unitary and propose a column generation approach based on a
Dantzig-Wolfe reformulation of the problem, where each column represents a feasible vehicle route
associated with a compatible purchasing plan.Two different procedures are introduced to solve the
pricing problem, namely a labeling algorithm solving a Resource-Constrained Elementary Shortest
Path Problem on an expanded graph, and a tailored branch-and-cut algorithm. Due to the integrality
request on variables, we embed the column generation in a branch-and-bound framework and propose
different branching rules, thus obtaining a branch-and-price procedure. Extensive tests, carried out on
a large set of instances, show that our branch-and-price method performs well, improving on average,
both in quality and in computational time, solutions obtained by a branch-and-cut approach existing in
the literature that relies on a three-index connectivity constraints based formulation
Gendreau et al. (2006) data set
No full textGendreau et al.’s (2006) benchmark instances consist of 27 problem instances, with the number of customers varying between 15 and 100. The nodes’ coordinates, the weights demanded by the customers, and the vehicle weight capacities were taken from the CVRP instances of Toth and Vigo (2002). The loading space was defined as W = 25, H = 30, and L = 60. The loading space of the vehicles and widths, lengths, and heights of requested items were generated by Gendreau et al. (2006).THIS DATASET IS ARCHIVED AT DANS/EASY, BUT NOT ACCESSIBLE HERE. TO VIEW A LIST OF FILES AND ACCESS THE FILES IN THIS DATASET CLICK ON THE DOI-LINK ABOV
Optimizing daily agent scheduling in a multiskill call center
No full textWe examine and compare simulation-based algorithms for solving the agent scheduling problem in a multiskill call center. This problem consists in minimizing the total costs of agents under constraints on the expected service level per call type, per period, and aggregated. We propose a solution approach that combines simulation with integer or linear programming, with cut generation. In our numerical experiments with realistic problem instances, this approach performs better than all other methods proposed previously for this problem. We also show that the two-step approach, which is the standard method for solving this problem, sometimes yield solutions that are highly suboptimal and inferior to those obtained by our proposed method.<br/
Hazmat routing by compulsory check points: a new risk mitigation strategy
No full textThis paper introduces a new strategy for the mitigation of risk due to hazardous material transportation on a road network. We propose to assign to each vehicle a compulsory check point to be crossed along the orgin destination trip. The authority locates k check points on the network and assigns one check point to each vehicle. Drivers will travel along the minimum cost itinerary which complies with the obligation. As the authority is risk driven and drivers are cost driven, we have to solve a bilevel optimization problem. We present computational results on literature benchmarcks that show the effectiveness of the method
A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints
No full textThis article addresses the well-known Capacitated Vehicle Routing Problem (CVRP), in the special case where the demand of a customer consists of a certain number of two-dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of the goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two-dimensional packing (2L) must be executed on each vehicle. The overall problem, denoted as 2L-CVRP, is NP-hard and particularly difficult to solve in practice. We propose a Tabu Search algorithm, in which the loading component of the problem is solved through heuristics, lower bounds, and a truncated branch-and-bound procedure. The effectiveness of the algorithm is demonstrated through extensivecomputational experiments
Heuristics for the traveling salesman problem with pickup and delivery
No full textWe consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD), an extension of the well-known Traveling Salesman Problem where each customer to be served is associated with two quantities of goods to be collected and delivered, respectively. A vehicle with given capacity starts at a depot and must visit each customer exactly once. The vehicle capacity must not be exceeded and the total length of the tour must be minimized. We describe new heuristics for TSPPD, the first based on the exact solution of a special case and the second based on tabu search, and we analyze their average performance through extensive computational experiments
- …
