A novel two-phase approach for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles: a case study on fuel delivery

Chowmali, W.; Sukto, S.

Growing Science » Decision Science Letters » A novel two-phase approach for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles: a case study on fuel delivery

Journals

DSL Volumes

Volume 1 (10)
- Issue 1 (5)
- Issue 2 (5)

Volume 2 (30)
- Issue 1 (5)
- Issue 2 (6)
- Issue 3 (9)
- Issue 4 (10)

Volume 3 (53)
- Issue 1 (15)
- Issue 2 (10)
- Issue 3 (19)
- Issue 4 (9)

Volume 4 (48)
- Issue 1 (10)
- Issue 2 (12)
- Issue 3 (14)
- Issue 4 (12)

Volume 5 (39)
- Issue 1 (12)
- Issue 2 (10)
- Issue 3 (8)
- Issue 4 (9)

Volume 6 (30)
- Issue 1 (8)
- Issue 2 (6)
- Issue 3 (9)
- Issue 4 (7)

Volume 7 (41)
- Issue 1 (8)
- Issue 2 (8)
- Issue 3 (8)
- Issue 4 (17)

Volume 8 (38)
- Issue 1 (8)
- Issue 2 (6)
- Issue 3 (14)
- Issue 4 (10)

Volume 9 (39)
- Issue 1 (8)
- Issue 2 (9)
- Issue 3 (14)
- Issue 4 (8)

Volume 10 (43)
- Issue 1 (7)
- Issue 2 (8)
- Issue 3 (20)
- Issue 4 (8)

Volume 11 (49)
- Issue 1 (9)
- Issue 2 (9)
- Issue 3 (14)
- Issue 4 (17)

Volume 12 (64)
- Issue 1 (12)
- Issue 2 (24)
- Issue 3 (13)
- Issue 4 (15)

Volume 13 (78)
- Issue 1 (21)
- Issue 2 (18)
- Issue 3 (19)
- Issue 4 (20)

Volume 14 (87)
- Issue 1 (21)
- Issue 2 (23)
- Issue 3 (25)
- Issue 4 (18)

Volume 15 (41)
- Issue 1 (19)
- Issue 2 (22)

Countries

Decision Science Letters

ISSN 1929-5812 (Online) - ISSN 1929-5804 (Print) Quarterly Publication Volume 9 Issue 1 pp. 77-90 , 2020

A novel two-phase approach for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles: a case study on fuel delivery Pages 77-90 Download PDF

Authors: Wasana Chowmali, Seekharin Sukto

DOI: 10.5267/j.dsl.2019.7.003

Keywords: Multi-compartment vehicle routing problem, Vehicle routing problem, General assignment problem, Fisher and Jaikumar Algorithm, Heuristic

Abstract: Distribution of goods is one of the main issues that directly affect the performance of the companies since efficient distribution of goods saves energy costs and also leads to reduced environmental impact. The multi-compartment vehicle routing problem (MCVRP) with a heterogeneous fleet of vehicles is encountered when dealing with this situation in many practical cases. This paper is motivated by the fuel delivery problem where the main objective of this research is to minimize the total driving distance using a minimum number of vehicles. Based on a case study of twenty petrol stations in northeastern Thailand, a novel two-phase heuristic, which is a variant of the Fisher and Jaikumar Algorithm (FJA), is proposed. The study first formulates an MCVRP model and then a mixed-integer linear programming (MILP) model is formulated for selecting the numbers and types of vehicles. A new clustering-based model is also developed in order to select the seed nodes and all customer nodes are considered as candidate seed nodes. The new Generalized Assignment Problem model (GAP model) is formulated to allocate the customers into each cluster. Finally, based on the traveling salesman problem (TSP), each cluster is solved in order to minimize the total driving distance. Numerical results show that the proposed heuristic is effective for solving the proposed model. The proposed algorithm can be used to minimize the total driving distance and the number of vehicles of the distribution network for fuel delivery.

How to cite this paper

 Chowmali, W & Sukto, S. (2020). A novel two-phase approach for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles: a case study on fuel delivery.Decision Science Letters , 9(1), 77-90.

Refrences

Avella, P., Boccia, M., & Sforza, A. (2004). Solving a fuel delivery problem by heuristic and exact approaches. European Journal of Operational Research, 152(1), 170-179.
Baker, B. M., & Sheasby, J. (1999). Extensions to the generalised assignment heuristic for vehicle routing. European Journal of Operational Research, 119(1), 147-157.
Benantar, A., Ouafi, R., & Boukachour, J. (2016). A petrol station replenishment problem: new variant and formulation. Logistics Research, 9(1), 6.
Benantar, A., Ouafi, R., & Boukachour, J. (2019). An improved tabu search algorithm for the petrol-station replenishment problem with adjustable demands. INFOR: Information Systems and Operational Research, 1-21..
Caramia, M., & Guerriero, F. (2010). A heuristic approach for the truck and trailer routing problem. Journal of the Operational Research Society, 61(7), 1168-1180.
Carotenuto, P., Giordani, S., Massari, S., & Vagaggini, F. (2015). Periodic capacitated vehicle routing for retail distribution of fuel oils. Transportation Research Procedia, 10, 735-744..
Casazza, M., Ceselli, A., & Calvo, R. W. (2018). A branch and price approach for the Split Pickup and Split Delivery VRP. Electronic Notes in Discrete Mathematics, 69, 189-196.
Chang, M. H., Cho, S., Kang, H. G., Yun, S. H., Song, K. M., Kim, D., & Chung, H. (2011). Process simulation for fuel delivery from storage and delivery system in fusion power plant. Fusion Engineering and Design, 86(9-11), 2200-2203..
Chokanat, P., Pitakaso, R., & Sethanan, K. (2019). Methodology to Solve a Special Case of the Vehicle Routing Problem: A Case Study in the Raw Milk Transportation System. AgriEngineering, 1(1), 75-93.
Coelho, L. C., & Laporte, G. (2015). Classification, models and exact algorithms for multi-compartment delivery problems. European Journal of Operational Research, 242(3), 854-864.
Cornillier, F., Boctor, F. F., Laporte, G., & Renaud, J. (2008). A heuristic for the multi-period petrol station replenishment problem. European Journal of Operational Research, 191(2), 295-305.
Cornillier, F., Boctor, F., & Renaud, J. (2012). Heuristics for the multi-depot petrol station replenishment problem with time windows. European Journal of Operational Research, 220(2), 361-369.
Cornillier, F., Laporte, G., Boctor, F. F., & Renaud, J. (2009). The petrol station replenishment problem with time windows. Computers & Operations Research, 36(3), 919-935..
De, A., Pratap, S., Kumar, A., & Tiwari, M. K. (2018). A hybrid dynamic berth allocation planning problem with fuel costs considerations for container terminal port using chemical reaction optimization approach. Annals of Operations Research, 1-29.
El Fallahi, A., Prins, C., & Calvo, R. W. (2008). A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, 35(5), 1725-1741..
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Gutierrez-Rodríguez, A. E., Conant-Pablos, S. E., Ortiz-Bayliss, J. C., & Terashima-Marín, H. (2019). Selecting meta-heuristics for solving vehicle routing problems with time windows via meta-learning. Expert Systems with Applications, 118, 470-481.
Gutierrez, A., Dieulle, L., Labadie, N., & Velasco, N. (2018). A multi-population algorithm to solve the VRP with stochastic service and travel times. Computers & Industrial Engineering, 125, 144-156.
Hanum, F., Hadi, M., Aman, A., & Bakhtiar, T. (2019). Vehicle routing problems in rice-for-the-poor distribution. Decision Science Letters, 8(3), 323-338.
Islam, M., Ghosh, S., & Rahman, M. (2015). Solving Capacitated Vehicle Routing Problem by Using Heuristic Approaches: A Case Study. Journal of Modern Science and Technology, 3(1), 135-146.
Kallestrup, K. B., Lynge, L. H., Akkerman, R., & Oddsdottir, T. A. (2014). Decision support in hierarchical planning systems: The case of procurement planning in oil refining industries. Decision Support Systems, 68, 49-63.
Chopra, S., & Meindl, P. (2007). Supply chain management. Strategy, planning & operation. In Das summa summarum des management (pp. 265-275). Gabler.
Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 7(4), 326-329.
Ng, W. L., Leung, S. C. H., Lam, J. K. P., & Pan, S. W. (2008). Petrol delivery tanker assignment and routing: a case study in Hong Kong. Journal of the Operational Research Society, 59(9), 1191-1200.
Popović, D., Vidović, M., & Radivojević, G. (2012). Variable neighborhood search heuristic for the inventory routing problem in fuel delivery. Expert Systems with Applications, 39(18), 13390-13398.
Prescott-Gagnon, E., Desaulniers, G., & Rousseau, L. M. (2014). Heuristics for an oil delivery vehicle routing problem. Flexible Services and Manufacturing Journal, 26(4), 516-539.
Salavati-Khoshghalb, M., Gendreau, M., Jabali, O., & Rei, W. (2019). An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy. European Journal of Operational Research, 273(1), 175-189.
Surjandari, I., Rachman, A., Dianawati, F., & Wibowo, R. P. (2011). Petrol delivery assignment with multi-product, multi-depot, split deliveries and time windows. International Journal of Modeling and Optimization, 1(5), 375.
Vidović, M., Popović, D., & Ratković, B. (2014). Mixed integer and heuristics model for the inventory routing problem in fuel delivery. International Journal of Production Economics, 147, 593-604.
Wichapa, N., & Khokhajaikiat, P. (2017). Using the hybrid fuzzy goal programming model and hybrid genetic algorithm to solve a multi-objective location routing problem for infectious waste disposal. Journal of Industrial Engineering and Management, 10(5), 853-886.
Wichapa, N., & Khokhajaikiat, P. (2018). Solving a multi-objective location routing problem for infectious waste disposal using hybrid goal programming and hybrid genetic algorithm. International Journal of Industrial Engineering Computations, 9(1), 75-98.
Yu, L., Yang, Z., & Tang, L. (2016). Prediction-based multi-objective optimization for oil purchasing and distribution with the NSGA-II algorithm. International Journal of Information Technology & Decision Making, 15(02), 423-451.