Multi-objective MDVRP solution considering route balance and cost using the ILS metaheuristic

Abstract: The multi-objective problem of multi-depot vehicle routing (MOMDVRP) is proposed by considering the minimization of the traveled arc costs and the balance of routes. Seven mathematical models were reviewed to determine the route balance equation and the best-performing model is selected for this purpose. The solution methodology consists of three stages; in the first one, beginning solutions are built up by means of a constructive heuristic. In the second stage, fronts are constructed from each starting solution using the iterated local search multi-objective metaheuristics (ILSMO). In the third stage, we obtain a single front by using concepts of dominance, taking as a base the fronts of the previous stage. Thus, the first two fronts are taken and a single front is formed that corresponds to the current solution of the problem; next the third front is added to the current Pareto front of the problem, the procedure is repeated until exhaustion of the list of the fronts initially obtained. The resulting front is the solution to the problem. To validate the methodology we use instances from the specialized literature, which have been used for the multi-depot routing problem (MDVRP). The results obtained provide very good quality. Finally, decision criteria are used to select the most appropriate solution for the front, both from the point of view of the balance and the route cost.

How to cite this paper

 Galindres-Guancha, L., Toro-Ocampo, E & Rendón, R. (2018). Multi-objective MDVRP solution considering route balance and cost using the ILS metaheuristic.International Journal of Industrial Engineering Computations , 9(1), 33-46.

Refrences

Cordeau, J. F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi‐depot vehicle routing problems. Networks, 30(2), 105-119.
Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T. (2000, September). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In International Conference on Parallel Problem Solving From Nature (pp. 849-858). Springer Berlin Heidelberg.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
Duarte, A., Pantrigo, J. J., Pardo, E. G., & Mladenovic, N. (2015). Multi-objective variable neighborhood search: an application to combinatorial optimization problems. Journal of Global Optimization, 63(3), 515-536.
Geiger, M. J. (2008). Foundations of the Pareto iterated local search metaheuristic. arXiv preprint arXiv:0809.0406.
Halvorsen-Weare, E. E., & Savelsbergh, M. W. (2016). The bi-objective mixed capacitated general routing problem with different route balance criteria. European Journal of Operational Research, 251(2), 451-465.
Ho, W., Ho, G. T., Ji, P., & Lau, H. C. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21(4), 548-557.
Keskinturk, T., & Yildirim, M. B. (2011, June). A genetic algorithm metaheuristic for bakery distribution vehicle routing problem with load balancing. In Innovations in Intelligent Systems and Applications (INISTA), 2011 International Symposium on (pp. 287-291). IEEE.
Kulkarni, R. V., & Bhave, P. R. (1985). Integer programming formulations of vehicle routing problems. European Journal of Operational Research, 20(1), 58-67.
Liefooghe, A., Humeau, J., Mesmoudi, S., Jourdan, L., & Talbi, E. G. (2012). On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems. Journal of Heuristics, 18(2), 317-352.
López, L., Hincapié, R. A., & Gallego, R. A. (2013). Planeamiento multiobjetivo de sistemas de distribución usando un algoritmo evolutivo nsga-ii (multiobjective distribution system planning using an nsga-ii evolutionary algorithm). Revista EIA, 8(15), 141-151.
Mladenovic, N., y Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100.
Montoya-Torres, J. R., Franco, J. L., Isaza, S. N., Jiménez, H. F., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115-129.
Paessens, H. (1988). The savings algorithm for the vehicle routing problem. European Journal of Operational Research, 34(3), 336-344.
Ribeiro, R., & Ramalhinho Dias Lourenço, H. (2001). A multi-objective model for a multi-period distribution management problem.
Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.
Schwarze, S., & Voß, S. (2013). Improved load balancing and resource utilization for the skill vehicle routing problem. Optimization Letters, 7(8), 1805-1823.