Abstract
In this paper, we present a solution method for a bi-objective vehicle routing problem, called the vehicle routing problem with route balancing (VRPRB), in which the total length and balance of the route lengths are the objectives under consideration. The method, called Target Aiming Pareto Search, is defined to hybridize a multi-objective genetic algorithm for the VRPRB using local searches. The method is based on repeated local searches with their own appropriate goals. We also propose an implementation of the Target Aiming Pareto Search using tabu searches, which are efficient meta-heuristics for the vehicle routing problem. Assessments with standard metrics on classical benchmarks demonstrate the importance of hybridization as well as the efficiency of the Target Aiming Pareto Search.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Ben Abdelaziz, F., Kricen, S., Chaouchi, J.: A hybrid heuristic for multiobjective knapsack problem. In: Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 205–212. Kluwer Academic, Dordrecht (1999)
Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (eds.): Combinatorial Optimization, pp. 315–338, Chapter 11. Wiley, Chichester (1979)
Corberan, A., Fernandez, E., Laguna, M., Marti, R.: Heuristic solutions to the problem of routing school buses with multiple objectives. J. Oper. Res. Soc. 53(4), 427–435 (2002)
Cordeau, J.-F., Gendreau, M., Laporte, G.: A tabu search heuristic for periodic and multi-depot vehicle problems. Networks 30, 105–119 (1997)
Cordeau, J.-F., Laporte, G., Mercier, A.: A unified tabu search heuristic for vehicle routing problem with time windows. J. Oper. Res. Soc. 52, 928–932 (2001)
Current, J., Marsh, M.: Multiobjective transportation network design and routing problems: taxonomy and annotation. Eur. J. Oper. Res. 65, 4–19 (1993)
Deb, K., Agrawal, S., Pratab, A., Meyunivan, T.: A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii. IEEE Trans. Evol. Comput. 6(2), 182–197 (April 2002)
Deb, K., Goel, T.: A hybrid multi-objective evolutionary approach to engineering shape design. In: Zitzler, E., et al. (eds.) Evolutionary Multi-Criterion Optimization. Lecture Notes in Computer Science, vol. 1993, pp. 385–399. Springer, New York (2001)
Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multi-objective combinatorial optimization. OR Spektrum 22, 425–460 (2000)
El-Sherbeny, N.: Resolution of a vehicle routing problem with multi-objective simulated annealing method. Ph.D. thesis, Faculté Polytechnique de Mons (2001)
Geiger, M.J.: Genetic algorithms for multiple objective routing. In: MIC’2001, pp. 349–353 (2001)
Gendreau, M., Hertz, A., Laporte, G.: A tabu search heuristic for the vehicle routing problem. Manag. Sci. 40, 1276–1290 (1994)
Hansen, M.P.: Tabu search for multiobjective optimization: MOTS. In: Multiple Criteria Decision Making (1997)
Hong, S.-C., Park, Y.-B.: A heuristic for a bi-objective vehicle routing with time window constraints. Int. J. Prod. Econ. 62, 249–258 (1999)
Ishibuchi, H., Yoshida, T., Murata, T.: Balance between genetic search and local search in hybrid evolutionary multi-criterion optimization algorithms. In: Cantu-Paz, E., et al. (eds.) Genetic and Evolutionary Computation Conference, pp. 1301–1308. Morgan Kaufmann (July 2002)
Jaszkiewicz, A.: Genetic local search for multi-objective combinatorial optimization. Eur. J. Oper. Res. 137, 50–71 (2002)
Jozefowiez, N., Semet, F., Talbi, E.-G.: Parallel and hybrid models for multi-objective optimization: application to the vehicle routing problem. In: Merelo Guervos, J.J., et al. (eds.) PPSN VII. Lecture Notes in Computer Science, vol. 2439, pp. 271–280. Springer, New York (September 2002)
Knowles, J., Corne, D.: On metrics for comparing nondominated sets. In: Congress on Evolutionary Computation (CEC’2002), vol. 1, pp. 711–726. IEEE Center (2002)
Knowles, J.D.: Local-search and hybrid evolutionary algorithms for Pareto optimization. Ph.D. thesis, University of Reading, Reading, UK (January 2002)
Lee, T., Ueng, J.: A study of vehicle routing problems with load-balancing. Int. J. Phys. Distrib. Logist. Manag. 29(10), 646–658 (1999)
Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of vehicle routing and scheduling problem. Networks 11, 221–227 (1981)
Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44, 2245–2269 (1965)
Morse, J.N.: Reducing the size of non-dominated set: pruning by clustering. Comput. Oper. Res. 7(1–2), 55–66 (1980)
Or, I.: Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking. Ph.D. thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL (1976)
Potvin, J.-Y., Bengio, S.: The vehicle routing problem with time windows part II: genetic search. INFORMS J. Comput. 8(2), 165–172 (1996)
Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 33(12), 1985–2002 (2006)
Rahoual, M., Kitoun, B., Mabed, M., Bachelet, V., Benameur, F.: Multicriteria genetic algorithms for the vehicle routing problem with time windows. In: MIC’2001, pp. 527–532 (2001)
Ribeiro, R., Loureno, H.R.: A multi-objective model for a multi-period distribution management problem. In: MIC’2001—4th Metaheuristics International Conference, pp. 97–102 (July 2001)
Rochat, Y., Taillard, E.: Probalistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995)
Serafini, P.: Simulated annealing for multiple objective optimization problems. In: The Tenth International Conference on Multiple Criteria Decision Making, vol. 1, pp. 87–96 (1992)
Silverman, B.W.: Density Estimation for Statistics and Data Analysis. Chapman and Hall, London (1986)
Sessomboon, W., Watanabe, K., Irohara, T., Yoshimoto, K.: A study on multi-objective vehicle routing problem considering customer satisfaction with due-time (the creation of Pareto optimal solutions by hybrid genetic algorithm). Trans. Jpn. Soc. Mech. Eng. 64, 1108–1115 (1998)
Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, vol. 9. SIAM (December 2001)
Ulungu, E.L.: Optimisation combinatoire multicritère: détermination de l’ensemble des solutions efficaces et méthodes interactives. Ph.D. thesis. Université de Mons-Hainaut (1993)
Zitzler, E.: Evolutionary algorithm for multiobjective optimization: methods and applications. Ph.D. thesis. Swiss Federal Institute of Technology (ETH), Zurich, Switzerland (November 1999)
Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: improving the strength pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland (2001)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jozefowiez, N., Semet, F. & Talbi, EG. Target aiming Pareto search and its application to the vehicle routing problem with route balancing. J Heuristics 13, 455–469 (2007). https://doi.org/10.1007/s10732-007-9022-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-007-9022-6