Abstract
In this study, a heuristic free from parameter tuning is introduced to solve the vehicle routing problem (VRP) with two conflicting objectives. The problem which has been presented is the designing of optimal routes: minimizing both the number of vehicles and the maximum route length. This problem, even in the case of its single objective form, is NP-hard. The proposed self-tuning heuristic (STH) is based on local search and has two parameters which are updated dynamically throughout the search process. The most important advantage of the algorithm is the application convenience for the end-users. STH is tested on the instances of a multi-objective problem in school bus routing and classical vehicle routing. Computational experiments, when compared with the prior approaches proposed for the multi-objective routing of school buses problem, confirm the effectiveness of STH. STH also finds high-quality solutions for multi-objective VRPs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alabas-Uslu C (2004). Birlesi Eniyileme Problemleri Icin Oto-Kontrollu Yerel Arama Yontemi. PhD thesis, Gazi University Institute of Science and Technology, Turkey.
Alabas-Uslu C and Dengiz B (2007). Self-controlled local search algorithm. Eur J Opl Res (under review process).
Battiti R and Tecchioli G (1994). The reactive tabu search. ORSA J Comput 6: 126–140.
Baugh JW, Kakivaya GKR and Stone JR (1998). Intractability of the dial-a-ride problem and a multiobjective solution using simulated annealing. Eng Optim 30: 91–123.
Bodin LD and Berman L (1979). Routing and scheduling of school buses by computer. Trans Sci 13: 113–129.
Bowerman R, Hall B and Calamai P (1995). A multiobjective optimization approach to urban school bus routing—formulation and solution method. Trans Res Part A—Policy Pract 29: 107–123.
Calvete HI, Gale C, Oliveros M-J and Sanchez-Valverde B (2005). A goal programming approach to vehicle routing problems with soft time windows. Eur J Opl Res 177: 1720–1733.
Chen D and Kallsen HA (1988). School bus routing and scheduling: an expert system approach. Comput Ind Eng 15: 179–183.
Christofides N and Eilon S (1969). An algorithm for the vehicle dispatching problem. Op Res Quart 20: 309–318.
Corberán A, Fernández E, Laguna M and Martí R (2002). Heuristic solutions to the problem of routing school buses with multiple objectives. J Opl Res Soc 53: 427–435.
Crainic TG and Laporte G (1998). Fleet Management and Logistics. Kluwer: Boston.
Ehrgott M (2000). Approximation algorithms for combinatorial multicriteria optimization problems. Int Trans Op Res 7: 5–31.
Ehrgott M and Gandibleux X (2000). A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22: 425–460.
Ehrgott M, Figueira J, and Gandibleux X (2006). Multiple objective discrete and combinatorial optimization. Ann Op Res 147: Special issue.
Gandibleux X, Sevaux M, Sorensen K, T'kindt V (2004). Metaheuristics for Multiobjective Optimisation, Lecture Notes in Economics and Mathematical Systems, vol. 535. Springer: Berlin.
Garey MR and Johnson DS (1979). Computers and Intractability. W.H. Freeman: San Francisco.
Jaszkiewicz A (2001). Multiple objective metaheuristic algorithms for combinatoria optimization. Habilitation thesis, 360, Poznan University of Technology, Poznan.
Jones DF, Mirrazavi SK and Tamiz M (2002). Multi-objective metaheuristics: An overview of the current state-of-the-art. Eur J Opl Res 137: 1–9.
Li LYO and Fu Z (2002). The school bus routing problem: a case study. J Opl Res Soc 53: 552–558.
Li F, Golden B and Wasil E (2005). Very large-scale vehicle routing: New test problems, algorithms and results. Comput Op Res 32: 1165–1179.
Madsen OBG, Ravn HF and Rygaard JM (1995). A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Ann Op Res 60: 193–208.
Murata T and Itai R (2005). Multi-objective vehicle routing problems using two-fold EMO algorithms to enhance solution similarity on non-dominated solutions. Lecture Notes Comput Sci 3410: 885–896.
Pacheco J and Marti R (2006). Tabu search for a multi-objective routing problem. J Opl Res Soc 57: 29–37.
Prins C (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Opns Res 31: 1985–2002.
Reimann M, Doerner K and Hartl RF (2004). D-Ants: saving based ants divide and conquer the vehicle routing problem. Comput Opns Res 31: 563–591.
Russell RA and Chiang W-C (2006). Scatter search for the vehicle routing problem with time windows. Eur J Opl Res 169: 623–637.
Tan KC, Chew YH and Lee LH (2006). A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems. Eur J Opl Res 172: 855–885.
Tarantilis CD, Kiranoudis CT and Vassiliadis VS (2002). A list based threshold accepting algorithm for the capacitated vehicle routing problem. J Comput Math 79: 537–553.
Tian P, Ma J and Zhang D-M (1999). Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation property: an investigation of generation mechanism. Eur J Opl Res 118: 81–94.
Toth P and Vigo P (2002). The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. SIAM: Philadelphia.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Alabas-Uslu, C. A self-tuning heuristic for a multi-objective vehicle routing problem. J Oper Res Soc 59, 988–996 (2008). https://doi.org/10.1057/palgrave.jors.2602409
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2602409