×

A new heuristic for the fleet size and mix vehicle routing problem. (English) Zbl 0723.90018

Summary: We address the problem of simultaneously selecting the composition and routing of a fleet of vehicles in order to service efficiently customers with known demands from a central depot. This problem is called the fleet size and mix vehicle routing problem (FSMVRP). The vehicle fleet may be heterogeneous. The objective is to find the fleet composition and a set of routes with minimum total cost, which includes routing cost and vehicle cost. We present a new savings heuristic based on successive route fusion. At each iteration, the best fusion is selected by solving a weighted matching problem. This provides a less myopic criterium than the usual savings heuristics. This algorithm is also very easy to implement. Computational results are provided for a number of benchmark problems in order to compare its performance to that of various other methods.

MSC:

90B06 Transportation, logistics and supply chain management
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altinkemer, K.; Gavish, B., A parallel savings heuristic for the delivery problem with a log \(Q\) error guarantees, Ops Res. Lett., 6, 149-158 (1987)
[2] Bodin, L.; Golden, B.; Assad, A.; Ball, M., Routing and scheduling of vehicles and crews—the state of art, Computers Ops Res., 10, 63-212 (1983)
[3] Burkard, R. F.; Derigs, U., Assignment and Matching Problems Solution Methods with Fortran Programs (1980), Springer: Springer Berlin
[4] Christofides, N., Vehicle routing, (Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. Rinnooy; Shmoeys, D. B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985), Wiley: Wiley Chichester) · Zbl 0571.90059
[5] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N.; Mingozzi, A.; Toth, P., Combinational Optimization (1979), Wiley: Wiley Chichester) · Zbl 0461.90067
[6] Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Ops Res., 12, 568-581 (1964)
[7] Dantzig, G. B.; Ramser, K. H., The truck dispatching problem, Ops Res., 12, 80-91 (1959) · Zbl 0995.90560
[8] Desrochers, M.; Verhoog, T. W., A matching based savings algorithm for the vehicle routing problem, (Working Paper GERAD-89-04 (1989), École des Hautes Études Commerciales: École des Hautes Études Commerciales Montréal) · Zbl 0723.90018
[9] Dror, M.; Levy, L., A vehicle routing improvement algorithm comparison of a “greedy” and a matching implementation for inventory routing, Computers Ops Res., 13, 33-45 (1986) · Zbl 0614.90061
[10] Eilon, S.; Watson-Gandy, C. D.T.; Christofides, N., Distribution Management: Mathematical Modeling and Practical Analysis (1971), Hafner: Hafner New York
[11] Fisher, M.; Jaikumar, R., A generalized assignment heuristic for vehicle routing, Networks, 11, 109-124 (1981)
[12] Gheysens, F.; Golden, B.; Assad, A., A comparison of techniques for solving the fleet size and mix vehicle routing problems, OR Spektrum, 6, 207-216 (1984) · Zbl 0549.90068
[13] (Golden, B. L.; Assad, A. A., Vehicle routing: methods and studies. Vehicle routing: methods and studies, Studies in Management Science and Systems, Vol. 16 (1988), North-Holland: North-Holland Amsterdam) · Zbl 0638.00043
[14] Golden, B.; Assad, A.; Levy, L.; Gheysens, E., The fleet size and mix vehicle routing problem, Computers Ops Res., 11, 49-65 (1984) · Zbl 0607.90043
[15] Jonker, R., Traveling salesman and assignment algorithms: design and implementation, (Doctoral dissertation (1986), University of Amsterdam)
[16] Jonker, R.; Volgenant, T., Non-optimal edges for the symmetric traveling salesman problem, Ops Res., 32, 837-846 (1984) · Zbl 0546.90095
[17] Laporte, G.; Nobert, Y., Exact algorithms for the vehicle routing problems, Ann. Discrete Math., 31, 147-184 (1987)
[18] Or, I., Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking, (Doctoral dissertation (1976), Northwestern University)
[19] Volgenant, A., Contributions to the solution of the traveling salesman problem and related problems, (Doctoral dissertation (1987), University of Amsterdam) · Zbl 0683.90096
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.