Proceedings of International Conference on Applied Innovation in IT
2018/03/13, Volume 6, Issue 1, pp.29-36
Modelling the Generalized Multi-objective Vehicle Routing Problem Based on Costs
Viktor Kubil, Vasily Mokhov, Dmitry Grinchenkov
Abstract: The following article addresses a complex combinatorial optimization and integer-programming problem, referred to as the vehicle routing problem, which is typically related to the field of transportation logistics. The aim of the research is to combine a set of objective functions, number of common generalizations and extensions of the problem, arising in distributed services or goods supply. For this purpose, literature on the subject has been analysed, leading to the mathematical modelling method being applied. At the current moment such complicated variants of the problem present high importance for research because of both practical applications and high complexity. The paper proposes a new generalized multi-objective vehicle routing problem with multiple depots and heterogeneous vehicles fleet with regard to various factors affecting costs. The problem statement is presented as a mixed integer linear program. Objectives scalarization approach is proposed in order to reduce decision-maker participation. Shortcomings of the single-criterion formulation and negative effects of replacing the criteria with constraints are shown. The results provide initial data for solving a large number of transportation problems that are reduced to the vehicle routing problem. In particular, the application of the ant colony optimization as a method for solving the problem is discussed.
Keywords: Multi-Objective Optimization, Mathematical Model, Vehicle Routing Problem, Combinatorial Optimization, Graph Theory
- J.P. Rodrigue, C. Comtois, and B. Slack, “The geography of transport systems”, Routledge, July 2013.
- W. Zhou, T. Song, F. He and X. Liu, “Multiobjective Vehicle Routing Problem with Route Balance Based on Genetic Algorithm”, Discrete Dynamics in Nature and Society, December 2013.
- B.L. Golden, S. Raghavan and E.A. Wasil, “The vehicle routing problem: latest advances and new challenges”, Springer Science & Business Media, 2008.
- P. Toth and D. Vigo, “Vehicle routing: problems, methods, and applications”, SIAM, December 2014.
- A. Goel and V. Gruhn. “A general vehicle routing problem”, European Journal of Operational Research, pp.650–660, 2008.
- V.N. Kubil and V.A. Mokhov, “On the application of swarm intelligence in the transport logistics problems”, Problems of modernization of engineering education in Russia: collection of scientific articles on problems of higher school, Platov South-Russian State Polytechnic University (NPI), Novocherkassk, pp.140-144, 2014. (rus)
- Y.L. Kostyuk, M.S. Pozhidaev, “New heuristics is proposed for approximate solution of Vehicle Routing Problem (VRP) with capacity restriction and metric distances between vertices”. Tomsk State University Journal, 2010. (rus)
- D. Vigo, “A heuristic algorithm for the asymmetric capacitated vehicle routing problem”, European Journal of Operational Research, Vol. 89, No. 1, pp.108–126, 1996.
- R. Herrero, A. Rodríguez, J. Cáceres-Cruz and A.A. Juan, “Solving vehicle routing problems with asymmetric costs and heterogeneous fleets”, Int. J. Advanced Operations Management, Vol. 6, No. 1, pp.58–80, 2014.
- W. Ho, G.T. Ho, P. Ji and H.C. Lau, “A hybrid genetic algorithm for the multi-depot vehicle routing problem”, Engineering Applications of Artificial Intelligence, pp.548-557, June 2008.
- C.D. Tarantilis, C.T. Kiranoudis, and V.S. Vassiliadis, “A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem”, European Journal of Operational Research, 152(1), pp.148-158, 2004.
- D.V. Grinchenkov and D.N. Kushchiy, “Principles of software development for support of decision-making based on integreted expert estimates”, J. University News. Electromechanics, no. 5, pp.69-73, 2012.
- H. Li, A. Lim, “A metaheuristic for the pickup and delivery problem with time windows”, International
- Journal on Artificial Intelligence Tools, pp.173-186, 2003.
- R. Dondo, and J. Cerda, “A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows”, European Journal of Operational Research, pp.1478-1507, 2007.
- V.N. Kubil and V.A. Mokhov, “Application of the ant colony algorithms in multi-objective optimization problems with changing conditions”, Information and telecommunication systems and technologies, Kemerovo, pp.80-81, 2015.
- J.E. Bell and P.R. McMullen, “Ant colony optimization techniques for the vehicle routing problem”, Advanced Engineering Informatics, 2004.
- V.A. Mokhov, V.N. Kubil, F.A. Turovski and V.S. Filatov, “On the classification of methods to improve efficiency of swarms metaheuristics”, Scientific and technical conference and exhibition of innovative projects, Platov South-Russian State Polytechnic University (NPI), Novocherkassk, pp.74-78, 2014.
- N. Jozefowiez, F. Semet and E.G. Talbi, “Multi-objective vehicle routing problems”, European journal of operational research, 2008, pp.293-309.
- V.N. Kubil and V.A. Mokhov, “Automation of fast food restaurant networks using ant colony optimization”, The theory, design methods, software and technical platform of corporate information systems, Platov South-Russian State Polytechnic University (NPI), Novocherkassk, pp.44-46, 2014.
- V.N. Kubil, “Optimization of the courier services performance based on ant colony algorithm”, Scientific and technical conference and exhibition of innovative projects, Platov South-Russian State Polytechnic University (NPI), Novocherkassk, pp.119-120, 2014.