A column generation approach to the heterogeneous fleet vehicle routing problem. (English) Zbl 1187.90094
Summary: We consider a vehicle routing problem with a heterogeneous fleet of vehicles having various capacities, fixed costs and variable costs. An approach based on column generation (CG) is applied for its solution, hitherto successful only in the vehicle routing problem with time windows. A tight integer programming model is presented, the linear programming relaxation of which is solved by the CG technique. A couple of dynamic programming schemes developed for the classical vehicle routing problem are emulated with some modifications to efficiently generate feasible columns. With the tight lower bounds thereby obtained, the branch-and-bound procedure is activated to obtain an integer solution. Computational experience with the benchmark test instances confirms that our approach outperforms all the existing algorithms both in terms of the quality of solutions generated and the solution time.
MSC:
| 90B20 | Traffic problems in operations research |
Software:
VRPReferences:
| [1] | Golden, B.; Assad, A.; Levy, L.; Gheysens, F., The fleet size and mix vehicle routing problem, Computers and Operations Research, 11, 49-66 (1984) · Zbl 0607.90043 |
| [2] | Salhi, S.; Rand, G. K., Incorporating vehicle routing into the vehicle fleet composition problem, European Journal of Operational Research, 66, 313-330 (1993) · Zbl 0775.90155 |
| [3] | Gheysens, F.; Golden, B.; Assad, A., A new heuristic for determining fleet size and composition, Mathematical Programming Study, 26, 233-236 (1986) · Zbl 0585.90064 |
| [4] | Gendreau, M.; Laporte, G.; Musaraganyi, C.; Taillard, E. D., A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Computers and Operations Research, 26, 1153-1173 (1999) · Zbl 0967.90019 |
| [5] | Salhi, S.; Sari, M.; Saidi, D.; Touati, N., Adaptation of some vehicle fleet mix heuristics, Omega, 20, 653-660 (1992) |
| [6] | Wassan, N. A.; Osman, I. H., Tabu search variants for the mix fleet vehicle routing problem, Journal of the Operational Research Society, 53, 768-782 (2002) · Zbl 1130.90311 |
| [7] | Taillard, E. D., A heuristic column generation method for the heterogeneous fleet VRP, RAIRO, 33, 1-14 (1999) · Zbl 0992.90008 |
| [8] | Tarantilis, C. D.; Kiranoudis, C. T.; Vassiliadis, V. S., A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem, European Journal of Operational Research, 152, 148-158 (2004) · Zbl 1045.90007 |
| [9] | Desrochers, M.; Verhoog, T. W., A new heuristic for the fleet size and mix vehicle routing problem, Computers and Operations Research, 18, 263-274 (1991) · Zbl 0723.90018 |
| [10] | Renaud, J.; Boctor, F. F., A sweep-based algorithm for the fleet size and mix vehicle routing problem, European Journal of Operational Research, 140, 618-628 (2002) · Zbl 0998.90016 |
| [11] | Gheysens, F.; Golden, B.; Assad, A., A comparison of techniques for solving the fleet size and mix vehicle routing problem, Operations Research Spektrum, 6, 207-216 (1984) · Zbl 0549.90068 |
| [12] | Desrochers, M.; Desrosiers, J.; Solomon, M., A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, 40, 342-354 (1992) · Zbl 0749.90025 |
| [13] | Kohl, N.; Desrosiers, J.; Madsen, O. B.G.; Solomon, M. M.; Soumis, F., 2-path cuts for the vehicle routing problem with time windows, Transportation Science, 33, 101-116 (1999) · Zbl 1004.90015 |
| [14] | Bramel, J.; Simchi-Levi, D., On the effectiveness of set covering formulations for the vehicle routing problem with time windows, Operations Research, 45, 295-301 (1997) · Zbl 0890.90054 |
| [15] | Christofides, N.; Mingozzi, A.; Toth, P., State-space relaxation procedures for the computation of bounds to routing problems, Networks, 11, 145-164 (1981) · Zbl 0458.90071 |
| [16] | Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Mathematical programming, 20, 255-282 (1981) · Zbl 0461.90067 |
| [17] | Gelinas, S.; Desrochers, M.; Desrosiers, J.; Solomon, M. M., A new branching strategy for time constrained routing problems with application to backhauling, Annals of Operations Research, 61, 91-109 (1995) · Zbl 0839.90029 |
| [18] | Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501 |
| [19] | Savelsbergh, M., A branch-and-price algorithm for the generalized assignment problem, Operations Research, 45, 831-841 (1997) · Zbl 0895.90161 |
| [20] | Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W.P.; Vance, P. H., Branch-and-price: column generation for solving huge integer programs, Operations Research, 46, 316-329 (1998) · Zbl 0979.90092 |
| [21] | Dror, M., Note on the complexity of the shortest path models for column generation in VRPTW, Operations Research, 42, 977-978 (1994) · Zbl 0815.90064 |
| [22] | Desrochers, M.; Soumis, F., A reoptimization algorithm for the shortest path problem with time windows, European Journal of Operational Research, 35, 242-254 (1988) · Zbl 0677.90080 |
| [23] | Kolen, A. W.J.; Rinnooy Kan, A. H.G.; Trienekens, H. W.J. M., Vehicle routing with time windows, Operations Research, 35, 266-273 (1987) · Zbl 0636.90047 |
| [24] | Houck, D. J.; Picard, J. C.; Queyranne, M.; Vemuganti, R. R., The traveling salesman problem as a constrained shortest path problem: theory and computational experience, Opsearch, 17, 93-109 (1980) · Zbl 0446.90084 |
| [25] | Desrochers M, An algorithm for the shortest path problem with resource constraints. Cahiers du GERAD G-88-27, Ecole des H.E.C., Montreal, Canada.; Desrochers M, An algorithm for the shortest path problem with resource constraints. Cahiers du GERAD G-88-27, Ecole des H.E.C., Montreal, Canada. · Zbl 0641.90083 |
| [26] | Fukasawa, R.; Lysgaard, J.; de Aragao, M. P.; Reis, M.; Uchoa, E.; Werneck, R. F., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Lecture Notes in Computer Science, 3064, 1-15 (2004) · Zbl 1092.90540 |
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.
