Abstract
This paper addresses the multi-compartment and multi-trip vehicle routing problem in a fuel distribution company. A decision support system (DSS) to automatically produce daily routing plans was developed. The company delivers three fuel types using a heterogeneous fleet of multi-compartmented vehicles with a maximum capacity expressed in fuel liters. Additional and real constraints are imposed, such as time windows and compulsory breaks. A constructive heuristic based on the Clarke and Wright savings algorithm was adapted in order to embed all business constraints. This constructive heuristic was developed in three steps. In the first step, all the previously mentioned constraints were taken into account. In the second version of the algorithm, the multi-trip case was incorporated. In order to improve the quality of the solution, an exchange of compartments mechanism and two local search procedures were developed. One of the local procedures was based on local search movements within each route, while the other one was based on movements between distinct routes. Solutions are displayed using a georeferenced-based platform allowing for a spatial representation of data to be analyzed. The achieved results show that the total traveled distance can be reduced by approximately 14%. The main contribution of this work is to offer the company a DSS for route planning without any additional cost that may enable fast and efficient planning of the entire company’s distribution sector.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Avella, P., Boccia, M., Sforza, A.: Solving a fuel delivery problem by heuristic and exact approaches. Eur. J. Oper. Res. 152(1), 170–179 (2004)
Baldacci, R., Bartolini, E., Mingozzi, A., Roberti, R.: An exact solution framework for a broad class of vehicle routing problems. CMS 7(3), 229–268 (2010)
Brown, G.G., Graves, G.W.: Real-time dispatch of petroleum tank trucks. Manage. Sci. 27(1), 19–32 (1981)
Cardoso, V.M.: The road transport of dangerous goods in Portugal (O transporte rodoviário de mercadorias perigosas em Portugal). Revista Segurança 224, 22–27 (2015)
Cattaruzza, D., Absi, N., Feillet, D., Vidal, T.: A memetic algorithm for the multi trip vehicle routing problem. Eur. J. Oper. Res. 236(3), 833–848 (2014)
Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4), 568–581 (1964)
Coelho, L.C., Laporte, G.: Classification, models and exact algorithms for multi-compartment delivery problems. Eur. J. Oper. Res. 242(3), 854–864 (2015)
Cornillier, F., Boctor, F., Renaud, J.: Heuristics for the multi-depot petrol station replenishment problem with time windows. Eur. J. Oper. Res. 220(2), 361–369 (2012)
Cornillier, F., Boctor, F.F., Laporte, G., Renaud, J.: An exact algorithm for the petrol station replenishment problem. J. Oper. Res. Soc. 59(5), 607–615 (2008)
Cornillier, F., Boctor, F.F., Laporte, G., Renaud, J.: A heuristic for the multi-period petrol station replenishment problem. Eur. J. Oper. Res. 191(2), 295–305 (2008)
Cornillier, F., Laporte, G., Boctor, F.F., Renaud, J.: The petrol station replenishment problem with time windows. Comput. Oper. Res. 36(3), 919–935 (2009)
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959)
Erdoğan, G.: An open source spreadsheet solver for vehicle routing problems. Comput. Oper. Res. 84, 62–72 (2017)
Lin, C., Choy, K.L., Ho, G.T., Lam, H., Pang, G.K., Chin, K.S.: A decision support system for optimizing dynamic courier routing operations. Expert Syst. Appl. 41(15), 6917–6933 (2014)
Mendoza, J.E., Castanier, B., Guéret, C., Medaglia, A.L., Velasco, N.: A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Comput. Oper. Res. 37(11), 1886–1898 (2010)
Mester, D., Bräysy, O.: Active guided evolution strategies for large-scale vehicle routing problems with time windows. Comput. Oper. Res. 32(6), 1593–1614 (2005)
Muyldermans, L., Pang, G.: On the benefits of co-collection: experiments with a multi-compartment vehicle routing algorithm. Eur. J. Oper. Res. 206(1), 93–103 (2010)
Ng, W.L., Leung, S., Lam, J., Pan, S.: Petrol delivery tanker assignment and routing: a case study in Hong Kong. J. Oper. Res. Soc. 59(9), 1191–1200 (2008)
Pena, C.M.D., Pinto, T., Carvalho, M.S.: A constructive heuristic for the multi-compartment vehicle routing problem: an approach for a fuel distribution company (2017)
Popović, D., Vidović, M., Radivojević, G.: Variable neighborhood search heuristic for the inventory routing problem in fuel delivery. Expert Syst. Appl. 39(18), 13390–13398 (2012)
Ramos, T.R.P., de Morais, C.S., Barbosa-Póvoa, A.P.: The smart waste collection routing problem: alternative operational management approaches. Expert Syst. Appl. 103, 146–158 (2018)
Rizzoli, A.E., Montemanni, R., Lucibello, E., Gambardella, L.M.: Ant colony optimization for real-world vehicle routing problems. Swarm Intell. 1(2), 135–151 (2007)
Santos, L., Coutinho-Rodrigues, J., Antunes, C.H.: A web spatial decision support system for vehicle routing using google maps. Decis. Support Syst. 51(1), 1–9 (2011)
Toth, P., Vigo, D.: Vehicle routing: problems, methods, and applications. Soc. Ind. Appl. Math. (2014)
Vidović, M., Popović, D., Ratković, B.: Mixed integer and heuristics model for the inventory routing problem in fuel delivery. Int. J. Prod. Econ. 147, 593–604 (2014)
Wang, L., Kinable, J., Van Woensel, T.: The fuel replenishment problem: a split-delivery multi-compartment vehicle routing problem with multiple trips. Comput. Oper. Res. 118, 104904 (2020)
Acknowledgements
This research is sponsored by national funds through FCT – Fundação para a Ciência e a Tecnologia, under the project UIDB/00285/ 2020. This work has been also supported by FCT – Fundação para a Ciência e Tecnologia within the R&D Units Project Scope: UIDB/00319/2020.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Pena, C., Pinto, T., Carvalho, M.S. (2021). A Two-Stage Heuristic for a Real Multi-compartment and Multi-trip Vehicle Routing Problem with Time Windows. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2021. ICCSA 2021. Lecture Notes in Computer Science(), vol 12953. Springer, Cham. https://doi.org/10.1007/978-3-030-86976-2_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-86976-2_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86975-5
Online ISBN: 978-3-030-86976-2
eBook Packages: Computer ScienceComputer Science (R0)