On Modelling and Solving Heterogeneous Vehicle Routing Problem with Multi-Trips and Multi-Products





Heterogeneous Vehicle Routing Problem, Multi-Trips, Multi-Products, Mixed Integer Linear Programming, Genetic Algorithm


Vehicle routing problem (VRP) is a model to determine an optimal routing plan for a fleet of homogeneous vehicles to serve a set customer which some operational constraints are satisfied. In most practical distribution problems, customer demands are served using heterogeneous fleet of vehicles. This kind of VRP is called Heterogeneous Vehicle Routing Problem (HVRP). HVRP has evolved into a rich research area because of its practical. There were many studies of rich extensions of the standar HVRP. This research aims to enrich the extentions of HVRP which is motivated by real case in one of pharmacy distribution company in Indonesia which is delivered multi-products to its 55 customers by allowing some vehicles which has small capacity to perform multi-trips. This problem is called Heterogeneous Vehicle Routing Problem with Multi-Trips and Multi-Products (HVRPMTMP).

The mixed integer linear programming is developed based on four-index vehicle flow formulation. The model can be used generally in the same context of distribution problem. HVRPMTMP is generally NP-Hard problem, so the computational time using branch and bound in LINGO 16.0 is increasing exponentially by increasing the number of customers. Genetic algorithm is proposed to solve the real case. The result of the proposed GA can reduce the total cost from Rp 352540.6,- to Rp 180555,- or 48.78% from the current company policy.

Author Biographies

Fran Setiawan, Universitas Katolik Parahyangan

Lecturer in Industrial Engineering Department

Universitas Katolik Parahyangan

Nur Aini Masruroh, Universitas Gadjah Mada

Lecturer in Mechanical and Industrial Engineering Department

Universitas Gadjah Mada


Baldacci, R., Battara, M. and Vigo, D., Routing a Heterogeneous Fleet of Vehicles. The Vehicle Routing Problem: Latest Advances and New Challenges, 2008, pp. 1-25.

Braekers, K., Ramaekers, K., Nieuwenhuyse, I.V., (2015). The Vehicle Routing Problem: State of the Art Classification and Review. Computers & Industrial Engineering, 99, 2015, pp. 300-313.

Coelho, V.N., Grasas, A., Ramalhinho, H., Coelho, I.M., Souza, M.J.F., Cruz, R.C., An ILS-based Algorithm to Solve a Large-Scale Real Heterogeneous Fleet VRP with Multi-Trips and Docking Constraints, European Journal of Operational Research, 250, 2016 pp. 367-376.

Cordeau, J-F, Gendreau, M., Laporte.G., Potvin, J–Y,. and Semet, F., A Guide to Vehicle Routing Heuristics. Journal of the Operational Research Society, 53(5), 2002, pp. 512-522.

Cordeau, J-F., Laporte, G., Savelsbergh, M.W.P., Vigo, D., Barnhart, C. and Laporte, G. (2007). Vehicle Routing. Handbook in Operational Research and Management Science, 14, 2007, pp. 367-428.

Cruz, J.C., Grasas, A., Ramalhinho, H., and Juan, A.A., A Saving-Based Randomized Heuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem with Multi-Trips. Journal of Applied Operational Research, 2014, pp. 69-81.

Dantzig, G.B, and Ramser, J.H., The Truck Dispatching Problem. Management Science, 6, 1959, pp. 80-91.

De la Cruz, J.J., Paternina-Arboleda, C.D., Cantillo, V., and Montoya-Torres, J.R., A Two-Pheromone Trail Ant Colony System-Tabu Search Approach for the Heterogeneous Vehicle Routing Problem with Time Windows and Multiple Products. Journal of Heuristics, 19, 2013, pp. 233-252.

Gen, M, and Cheng, R., Genetic Algorithm and Engineering Optimization, 2000 John Wiley & Sons, Inc.

Gendreau, M., Potvin, J.Y., Braysy, O., Hasle, G. and Lokketangen, A., Metaheuristic for the Vehicle Routing Problem and its Extension: A Categorized Bibliography. CIRRELT, 2007

Huang, C, and Lee, C.M., A Study of Multi-Trip Vehicle Routing Problem and Distribution Centre Location Problem. POMS 22nd Annual Conference, 2011, Nevada, USA.

Koҫ, C., Bektas, T., Jabali, O., and Laporte, G., Thirty Years of Heterogeneous Vehicle Routing. European Journal of Operational Research, 2015, pp. 1-21.

Laporte, G., The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms, European Journal of Operations Research, 59, 1992, pp. 345-358.

Lathifah, A., Aplikasi Simulated Annealing Heuristik pada Permasalahan Heterogeneous Fleet Polution Routing Problem, Thesis in Master Program of Industrial Engineering Universitas Gadjah Mada, 2015, Yogyakarta

Montgomery, D.C., Design and Analysis of Experiments, 8th edition, 2013, John Wiley & Sons, New York

Pramuditha, Z.I., Optimasi Distribusi Multiple Products pada Multiple Buyers Menggunakan Multi-Vehicle pada Capacitated Vehicle Routing Problem. Thesis in Master Program of Industrial Engineering Universitas Gadjah Mada, 2014, Yogyakarta.

Prins, C., Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case. Journal of Mathematical Modelling and Algorithms, 1, 2002, pp. 135-150.

Prive, J., Renaud, J., Boctor, F. and Laporte, G., Solving a Vehicle Routing Problem Arising in Soft Drink Distribution. Journal of Operational Research Society, 2005

Santosa, B and Ai, T.J., Pengantar Metaheuristik: Implementasi dengan Matlab. ITS Tekno Sains, 2018, Surabaya.

Sexias, M.P. and Mendes, A.B., Column Generation for a Multitrip Vehicle Routing Problem with Time Windows, Drivers Work Hours and Heterogenous Fleet. Mathematical Problems in Engineering, 2013, pp. 1-13.

Shahsavar, M., Najafi, A.A, and Niaki, S.T.A., Statistical Design of Genetic Algorithm for Combinatorial Optimization Problems, Mathematical Problems in Engineering, 2011

Taillard, E.D., Laporte, G., and Gendreau, M., Vehicle Routing with Multiple Use of Vehicles. Journal of the Operational Research Society, 47 (8), 1996, pp. 1065-1070.

Talbi, E-G., Metaheuristic: From Design to Implementation, 2009 John Wiley & Sons, New Jersey

Toth, P., and Vigo D., Vehicle Routing: Problems, Methods, and Applications, 2014, Mathematical Optimization Society and Society for Industrial and Applied Mathematics (MOS-SIAM) series in optimization, Philadelphia