×

A sweep-based algorithm for the fleet size and mix vehicle routing problem. (English) Zbl 0998.90016

Summary: This paper presents a new sweep-based heuristic for the fleet size and mix vehicle routing problem. This problem involves two kinds of decisions: the selection of a mix of vehicles among the available vehicle types and the routing of the selected fleet. The proposed algorithm first generates a large number of routes that are serviced by one or two vehicles. The selection of routes and vehicles to be used is then made by solving to optimality, in polynomial time, a set-partitioning problem having a special structure. Results on a set of benchmark test problems show that the proposed heuristic produces excellent solutions in short computing times. Having a fast but good solution method is needed for transportation companies that rent a significant part of their fleet and consequently can take advantage of frequent changes in fleet composition. Finally, the proposed heuristic produced new best-known solutions for three of the test problems; these solutions are reported.

MSC:

90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization

Software:

VRP
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Boctor, F.F.; Renaud, J., The column-circular sub-sets selection problem: complexity and solutions, Computers and operation research, 27, 383-398, (2000) · Zbl 0973.90017
[2] Clarke, G.; Wright, J., Scheduling of vehicles from a central depot to a number of delivery points, Operations research, 12, 568-581, (1964)
[3] Cornuéjols, G.; Harche, F., Polyhedral study of the capacitated vehicle routing problem, Mathematical programming, 60, 21-52, (1993) · Zbl 0790.90029
[4] 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
[5] Etezadi, T.; Beasley, J.E., Vehicle fleet composition, Journal of the operational research society, 34, 87-91, (1983) · Zbl 0501.90055
[6] Fisher, M.; Jaikumar, M., A generalized assignment heuristic for vehicle routing, Networks, 11, 109-124, (1981)
[7] Foster, B.A.; Ryan, D.M., An integer programming approach to the vehicle scheduling problem, Operational research quarterly, 27, 377-384, (1976) · Zbl 0327.90030
[8] Gendreau, M.; Hertz, A.; Laporte, G., New insertion and post optimization procedures for the traveling salesman problem, Operations research, 40, 1086-1094, (1992) · Zbl 0767.90087
[9] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management science, 40, 1276-1290, (1994) · Zbl 0822.90053
[10] Gendreau, M.; Laporte, G.; Musaraganyi, Ch.; Taillard, E., A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Computers and operations research, 26, 1153-1173, (1999) · Zbl 0967.90019
[11] Gheysens, F.; Golden, B.; Assad, A., A comparison of techniques for solving the fleet size and mix vehicle routing problem, OR spektrum, 6, 207-216, (1984) · Zbl 0549.90068
[12] 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
[13] Gillett, B.; Miller, L., A heuristic for the vehicle dispatching problem, Operations research, 22, 340-349, (1974) · Zbl 0274.90013
[14] 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
[15] Gould, J., The size and composition of a road transport fleet, Operational research quarterly, 20, 81-92, (1969)
[16] Hadjiconstantinou, E.; Christofides, N.; Mingozzi, A., A new exact algorithm for the vehicle routing problem based on q-path and k-shortest paths relaxations, Annals of operations research, 61, 21-43, (1995) · Zbl 0839.90031
[17] Laporte, G., The traveling salesman problem: an overview of exact and approximate algorithms, European journal of operational research, 59, 231-247, (1992) · Zbl 0760.90089
[18] Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms, European journal of operational research, 59, 345-358, (1992) · Zbl 0761.90034
[19] Laporte, G.; Osman, I.H., Routing problems: A bibliography, Annals of operations research, 61, 227-262, (1995) · Zbl 0839.90032
[20] Lin, S., Computer solution of the traveling salesman problem, Bell system computer journal, 44, 2245-2269, (1965) · Zbl 0136.14705
[21] Or, I., 1976. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Doctoral Dissertation, Northwestern University
[22] Osman, I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of operations research, 41, 421-451, (1993) · Zbl 0775.90153
[23] Osman, I.; Salhi, S., Local search strategies for the vehicle fleet mix problem, (), 131-153
[24] Renaud, J.; Boctor, F.F.; Laporte, G., An improved petal heuristic for the vehicle routing problem, Journal of the operational research society, 47, 329-336, (1996) · Zbl 0851.90032
[25] Renaud, J.; Boctor, F.F.; Laporte, G., A fast composite heuristic for the symmetric traveling salesman problem, INFORMS journal on computing, 8, 134-143, (1996) · Zbl 0866.90131
[26] Rochat, Y.; Taillard, É.D., Probabilistic diversification and intensification in local search for vehicle routing, Journal of heuristics, 1, 147-176, (1995) · Zbl 0857.90032
[27] Ryan, D.M.; Hjorring, C.; Glover, F., Extension of the petal method for vehicle routing, Journal of the operational research society, 44, 289-296, (1993) · Zbl 0804.90043
[28] Salhi, S.; Rand, G.K., Improvement to vehicle routing heuristics, Journal of the operational research society, 38, 293-295, (1987)
[29] 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
[30] Salhi, S.; Sari, M.; Saidi, D.; Touati, N.A.C., Adaptation of some vehicle fleet mix heuristics, OMEGA international journal of management science, 20, 653-660, (1992)
[31] Taillard, É., Parallel iteration search methods for vehicle routing, Networks, 23, 661-673, (1993) · Zbl 0804.90045
[32] Taillard, É.D., A heuristic column generation method for the heterogeneous fleet VRP, Rairo, 33, 1-34, (1999) · Zbl 0992.90008
[33] Woods, D.G.; Harris, F.C., Truck fleet size composition for concrete distribution, International journal of physical distribution, 10, 3-14, (1979)
[34] Wren, A.; Holliday, A., Computer scheduling of vehicle from one or more depots to a number of delivery points, Operational research quarterly, 23, 333-344, (1972)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.