×

Vehicle routing problems with alternative paths: an application to on-demand transportation. (English) Zbl 1178.90037

Summary: The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin-destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.

MSC:

90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks
90C39 Dynamic programming

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Ahuja, R. K.; Hochbaum, D. S.; Orlin, J. B., Solving the convex cost integer dual network flow problem, Management Science, 49, 7, 950-964 (2003) · Zbl 1232.90317
[2] Akbar, M. M.; Rahman, M. S.; Kaykobad, M.; Manning, E. G.; Shoja, G. C., Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls, Computers and Operations Research, 33, 1259-1273 (2004) · Zbl 1104.90039
[3] Baldacci, R.; Bodin, L.; Mingozzi, A., The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem, Computers and Operations Research, 33, 9, 2667-2702 (2006) · Zbl 1086.90002
[4] Beasley, J. E.; Christofides, N., An algorithm for the resource constrained shortest path problem, Networks, 19, 379-394 (1989) · Zbl 0673.90085
[5] Bent, R.; Van Henteryck, P., A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers and Operations Research, 33, 4, 875-893 (2006) · Zbl 1079.90591
[6] Bielli, M.; Boulmakoul, A.; Mouncif, H., Object modeling and path computation for multimodal travel systems, European Journal of Operational Research, 175, 1705-1730 (2006) · Zbl 1142.90367
[7] Colorni, A.; Dorigo, M.; Maffioli, F.; Maniezzo, V.; Righini, G.; Trubian, M., Heuristics from nature for hard combinatorial optimization problems, International Transactions in Operational Research, 3, 1-21 (1996) · Zbl 0863.90120
[8] Cordeau, J.-F., A branch-and-cut algorithm for the dial-a-ride problem, Operations Research, 54, 573-586 (2006) · Zbl 1167.90681
[9] Cordeau, J.-F.; Laporte, G., The dial-a-ride problem (DARP): Variants, modeling issues and algorithms, 4OR: A Quarterly Journal of Operations Research, 1, 89-101 (2003) · Zbl 1097.90008
[10] Cordeau, J.-F.; Laporte, G., A tabu search heuristic algorithm for the static multi-vehicle dial-a-ride problem, Transportation Research B, 37, 579-594 (2003)
[11] Cordeau, J.-F.; Laporte, G., The dial-a-ride problem: Models and algorithms, Annals of Operations Research, 153, 1, 29-46 (2007) · Zbl 1157.90353
[12] Coslovich, L.; Pesenti, R.; Ukovich, W., A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem, European Journal of Operational Research, 175, 1605-1615 (2006) · Zbl 1142.90323
[13] Crainic, T. G.; Laporte, G., Fleet Management and Logistics (1998), Kluwer: Kluwer Boston, USA · Zbl 0933.00021
[14] Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M.M., Soumis, F., 2002. VRP with pickup and delivery. In: Toth, P., Vigo, D. (Eds.), The Vehicle Routing Problem, Philadelphia, 2002, pp. 225-242.; Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M.M., Soumis, F., 2002. VRP with pickup and delivery. In: Toth, P., Vigo, D. (Eds.), The Vehicle Routing Problem, Philadelphia, 2002, pp. 225-242. · Zbl 1076.90544
[15] (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2005), Springer) · Zbl 1084.90002
[16] Desrochers, M.; Soumis, F., A generalized permanent labelling algorithm for the shortest path problem with time windows, Transportation Science, 26, 3, 191-212 (1988) · Zbl 0652.90097
[17] Desrosiers, J.; Dumas, Y.; Solomon, M. M.; Soumis, F., Time constrained routing and scheduling, (Ball, M. O.; Magnanti, T. L.; Monna, C. L.; Nemhauser, G. I., Network Routing. Handbooks in Operations Research and Management Science (1995), North-Holland: North-Holland Amsterdam), 35-139 · Zbl 0861.90052
[18] Dumas, Y., Desrosiers, J., Soumis, F., 1989. Large scale multi-vehicle dial-a-ride systems. In: GERAD, Ecole des Hautes Etudes Commerciales, Montréal, G-89-30.; Dumas, Y., Desrosiers, J., Soumis, F., 1989. Large scale multi-vehicle dial-a-ride systems. In: GERAD, Ecole des Hautes Etudes Commerciales, Montréal, G-89-30.
[19] Dumas, Y.; Desrosiers, J.; Soumis, F., The pickup and delivery problem with time windows, European Journal of Operational Research, 54, 7-22 (1991) · Zbl 0736.90028
[20] Ehrgott, M.; Gandibleux, X., A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spectrum, 22, 425-460 (2000) · Zbl 1017.90096
[21] Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems, Networks, 44, 3, 216-229 (2004) · Zbl 1056.90014
[22] Guerriero, F.; Musmanno, R., Label correcting methods to solve multicriteria shortest path problems, Journal of Optimization Theory and Applications, 111, 3, 589-613 (2001) · Zbl 0984.90050
[23] Gutin, G.; Punnen, A. P., The Traveling Salesman Problem and Its Variations (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0996.00026
[24] Hifi, M.; Michrafy, M.; Sbihi, A., A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem, Computational Optimization and Applications, 33, 271-285 (2006) · Zbl 1103.90086
[25] Horn, M. E.T., Multi-modal and demand-responsive passenger transport systems: A modelling framework with embedded control systems, Transportation Research A, 36, 167-188 (2002)
[26] Horn, M. E.T., An extended model and procedural framework for planning multi-modal passenger journeys, Transportation Research B, 37, 641-660 (2003)
[27] Irnich, S.; Desaulniers, G., Shortest path problems with resource constraints, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2005), Springer), 33-66 · Zbl 1130.90315
[28] Jaw, J. J.; Odoni, A. R.; Psaraftis, H. N.; Wilson, N. H.M., A heuristic algorithm for the multi-vehicle many-to-many advance request dial-a-ride problem, Transportation Research B, 20B, 243-257 (1986)
[29] Jørgensen, R. M.; Larsen, J.; Bergvinsdottir, K. B., Solving the dial-a-ride problem using genetic algorithms, Journal of the Operational Research Society, 58, 1321-1331 (2007) · Zbl 1179.90035
[30] Josselin, D.; Genre-Grandpierre, C., Des transports à la demande pour répondre aux nouvelles formes de mobilité. le concept de modulobus, (Montulet, B.; etal., Mobilités et temporalités (2005), University of Saint-Louis: University of Saint-Louis Bruxelles), 151-164
[31] Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack Problems (2004), Springer · Zbl 1103.90003
[32] Li, H., Lim, A., 2001. A metaheuristic for the pickup and delivery problem with time windows. In: ICTAI 2001, Dallas, USA, 2001, pp. 160-170.; Li, H., Lim, A., 2001. A metaheuristic for the pickup and delivery problem with time windows. In: ICTAI 2001, Dallas, USA, 2001, pp. 160-170.
[33] Lu, Q.; Dessouky, M. M., An exact algorithm for the multiple vehicle pickup and delivery problem, Transportation Science, 38, 503-514 (2004)
[34] Madsen, O. B.G.; Ravn, H. R.; Rygaard, J. M., A heuristic algorithm for the a dial-a-ride problem with time windows, multiple capacities, and multiple objectives, Annals of Operations Research, 60, 193-208 (1995) · Zbl 0839.90033
[35] Melachrinoudisa, E.; Ilhan, A. B.; Min, H., A dial-a-ride problem for client transportation in a health-care organization, Computers and Operations Research, 34, 742-759 (2007) · Zbl 1120.90003
[36] Rekiek, B.; Delchambre, A.; Saleh, H. A., Handicapped person transportation: An application of the grouping genetic algorithm, Engineering Application of Artificial Intelligence, 19, 511-520 (2006)
[37] Ropke, S., 2005. Heuristic and exact algorithms for vehicle routing problems. PhD Thesis, University of Copenhagen (DIKU), 2005.; Ropke, S., 2005. Heuristic and exact algorithms for vehicle routing problems. PhD Thesis, University of Copenhagen (DIKU), 2005.
[38] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40, 4, 455-472 (2006)
[39] Ropke, S.; Cordeau, J.-F.; Laporte, G., Models and branch-and-cut algorithm for pick-up and delivery problems with time windows, Networks, 49, 4, 258-272 (2007) · Zbl 1141.90340
[40] Savelsbergh, M. W.P.; Sol, M., DRIVE: Dynamic routing of independent vehicles, Operations Research, 46, 474-490 (1998) · Zbl 0987.90511
[41] Sbihi, A., 2003. Les méthodes hybrides en optimisation combinatoire: Algorithmes exacts et heuristiques. PhD Thesis, Université Paris 1, 2003.; Sbihi, A., 2003. Les méthodes hybrides en optimisation combinatoire: Algorithmes exacts et heuristiques. PhD Thesis, Université Paris 1, 2003.
[42] Sexton, T.; Bodin, L. D., Optimizing single vehicle many-to-many operations with desired delivery times: I. Scheduling, Transportation Science, 19, 378-410 (1985) · Zbl 0608.90043
[43] Sexton, T.; Bodin, L. D., Optimizing single vehicle many-to-many operations with desired delivery times: II. Routing, Transportation Science, 19, 411-435 (1985) · Zbl 0618.90042
[44] Skriver, A. J.V.; Andersen, K. A., A label correcting approach for solving bicriterion shortest-path problems, Computers and Operations Research, 27, 507-524 (2000) · Zbl 0955.90144
[45] Toth, P., Vigo, D., 1996. Fast local search algorithms for the handicapped persons transportation problem. In: Osman, I.H., Kelly, J.P. (Eds.), Meta-heuristics: Theory and Applications, Boston, pp. 677-690.; Toth, P., Vigo, D., 1996. Fast local search algorithms for the handicapped persons transportation problem. In: Osman, I.H., Kelly, J.P. (Eds.), Meta-heuristics: Theory and Applications, Boston, pp. 677-690. · Zbl 0877.90035
[46] Toth, P.; Vigo, D., Heuristic algorithms for the handicapped persons transportation problem, Transportation Science, 31, 60-71 (1997) · Zbl 0888.90117
[47] Warburton, A., Approximation of pareto optima in multiple-objective, shortest-path problems, Operations Research, 35, 70-79 (1987) · Zbl 0623.90084
[48] Xiang, Z.; Chu, C.; Chen, H., A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints, European Journal of Operational Research, 174, 2, 1117-1139 (2006) · Zbl 1103.90022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.