×

A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. (English) Zbl 0947.90578

Summary: This paper describes a novel tabu search heuristic for the Multi-Trip Vehicle Routing and Scheduling Problem (MTVRSP). The method was developed to tackle real distribution problems, taking into account most of the constraints that appear in practice. In the MTVRSP, besides the constraints that are common to the basic vehicle routing problem, the following ones are present: during each day a vehicle can make more than one trip; the customers impose delivery time windows; the vehicles have different capacities considered in terms of both volume and weight; the access to some customers is restricted to some vehicles; the drivers’ schedules must respect the maximum legal driving time per day and the legal time breaks; the unloading times are considered.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90B20 Traffic problems in operations research

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barnes, J. W.; Laguna, M., A tabu search experience in production scheduling, (Glover, F.; Laguna, M.; Taillard, E.; de Werra, J. C.D., Annals of Operations Research, 41 (1993), Baltzer AG, Science Publishers: Baltzer AG, Science Publishers Basel, Switzerland), 141-156 · Zbl 0775.90205
[2] Brandão, J. C.S., A Decision Support System and Algorithms for the Vehicle Routing and Scheduling Problems, (Doctor of Philosophy Thesis (1994), Department of Management Science, Lancaster University) · Zbl 1140.90329
[3] Gendreau, M.; Hertz, A.; Laporte, G., New Insertion and post-optimization procedures for the traveling salesman problem, Operations Research, 40, 6, 1086-1094 (1992) · Zbl 0767.90087
[4] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing, Management Science, 40, 1276-1290 (1994) · Zbl 0822.90053
[5] Gendreau, M.; Hertz, A.; Laporte, G.; Stan, M., Ageneralized insertion heuristic for the traveling salesman problem with time windows, (Publication CRT-95-07 (1996), Centre de Recherche Sur les Transports, Université Montreal)
[6] Glover, F., Heuristics for integer programming using surrogate constraints, Decision Sciences, 8, 156-166 (1977)
[7] Glover, F., Tabu search - Part I, ORSA Journal on Computing, 1, 3, 190-206 (1989) · Zbl 0753.90054
[8] Glover, F., Tabu search - Part II, ORSA Journal on Computing, 2, 1, 4-31 (1990) · Zbl 0771.90084
[9] Glover, F.; Taillard, E.; de Werra, J. C.D., A user’s guide to tabu search, (Glover Laguna, F.; Taillard, E.; de Werra, J. C.D., Annals of Operations Research, 41 (1993), Baltzer AG, Science Publishers: Baltzer AG, Science Publishers Basel, Switzerland), 3-28 · Zbl 0772.90063
[10] Kelly, M. J.; Golden, B.; Assad, A., Large-scale controlled rounding using tabu search with strategic oscillation, (Glover, F.; Laguna, M.; Taillard, E.; de Werra, J. C.D., Annals of Operations Research, 41 (1993), Baltzer AG, Science Publishers: Baltzer AG, Science Publishers Basel, Switzerland), 69-84 · Zbl 0775.90291
[11] Koskosidis, Y. A.; Powell, W. B., Application of optimization based models on vehicle routing and scheduling problems with time windows constraints, Journal of Business Logistics, 11, 2, 101-128 (1990)
[12] Lenstra, J. K.; Rinnooy Kan, A. H.G., Complexity of vehicle routing and scheduling problems, Networks, 11, 221-227 (1981) · Zbl 0416.90049
[13] Mooney, E. L.; Rardin, R. L., Tabu search for a class of scheduling problems, (Glover, F.; Laguna, M.; Taillard, E.; de Werra, J. C.D., Annals of Operations Research, 41 (1993), Baltzer AG, Science Publishers: Baltzer AG, Science Publishers Basel, Switzerland), 69-84
[14] Potvin, J.; Lapalme, G.; Rousseau, J., Integration of AI and OR techniques for computer-aided algorithmic design in the vehicle routing domain, Journal of the Operational Research Society, 41, 517-525 (1990)
[15] Savelsbergh, M. W.P., Computer Aided Routing, (Doctoral Dissertation (1988), Centrum voor Wiskunde en Informatics: Centrum voor Wiskunde en Informatics Amsterdam) · Zbl 0793.90019
[16] Rochat, Y.; Semet, F., A tabu search approach for delivering pet food and flour in switzerland, Journal of the Operational Research Society, 45, 1233-1246 (1994) · Zbl 0812.90044
[17] Semet, F.; Taillard, E., Solving real-life vehicle routing problems efficiently using tabu search, (Glover, F.; Laguna, M.; Taillard, E.; de Werra, J. C.D., Annals of Operations Research, 41 (1993), Baltzer AG, Science Publishers: Baltzer AG, Science Publishers Basel, Switzerland), 469-488 · Zbl 0775.90156
[18] Taillard, E., Robust tabu search for the quadratic assignment problem, Parallel Computing, 17, 443-455 (1991)
[19] Taillard, E.; Laporte, G.; Gendreau, M., Vehicle routing with multiple use of vehicles, Journal of the Operational Research Society, 47, 1065-1070 (1996) · Zbl 0864.90045
[20] Vliet, A.; Boender, C. G.E.; Rinnooy Kan, A. H.G., Interactive optimization of bulk sugar deliveries, Interfaces, 22, 3, 4-14 (1992)
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.