Abstract
We formulate the two-echelon routing problem considering multiple depots and heterogeneous fleets. Our study (a) presents a Mixed Integer Linear Programming (MILP) formulation with load-dependent fuel minimization objective, (b) uses driving cycles to represent speed variations along a path, (c) allows the vehicles to return to any depot/satellite, and (d) conserves the total number of vehicles at each depot/satellite. We call the problem a Multi-Depot Two-Echelon Fuel Minimizing Routing Problem (MD2E-FMRP). Prior studies assumed there is a fixed number of vehicles available at each satellite/depot, whereas we allow different number of vehicles of each vehicle type at each satellite and depot. Our formulation relaxes several unrealistic assumptions in existing two-echelon formulations and hence has greater practical application. Despite the relaxation of constraints, the running time of our model is comparable to existing formulations. Gurobi optimizer is used to find a better upper bound for up to 56 node instances within a given time limit of 10,000s. We also propose an Adaptive Large Neighborhood Search (ALNS) based heuristic solution technique that outperformed Gurobi in all the tested instances of MD2E-FMRP. We observe an average saving of 13.11% in fuel consumption by minimizing fuel consumed instead of minimizing distance. In general, adapting heterogeneous fleets results in fuel savings and consequently lower emissions compared to using a homogeneous fleet.
Similar content being viewed by others
References
Abdulkader MM, Gajpal Y, ElMekkawy TY (2018) Vehicle routing problem in omni-channel retailing distribution systems. Int J Prod Econ 196:43–55
Barth M, Scora G, Younglove T (2004) Modal Emissions Model for Heavy-duty Diesel Vehicles. Transp Res Rec J Transp Res Board 1880:10–20
Barth M, Younglove T, Scora G (2005) Development of a Heavy-duty Diesel Modal Emissions and Fuel Consumption Model. Technical report. University of California, Riverside
Bathmanabhan S, Madanayak SNS (2010) Analysis and interpretation of particulate matter- PM10, PM2.5 and PM1 emissions from the heterogeneous traffic near an urban roadway. Atmos Pollut Res 1(3):184–194. https://doi.org/10.5094/APR.2010.024. ISSN 1309-1042.
Bektas T, Laporte G (2011) The Pollution-Routing problem. Transp Res B Methodol 45:1232–1250
Boccia M, Crainic TG, Sforza A, Sterle C (2010) A Metaheuristic for a Two Echelon Location-Routing Problem. In: Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island. Proceedings. Springer, pp 288–301
Boccia M, Crainic TG, Sforza A, Sterle C (2011) Location-routing Models for Designing a Two-echelon Freight Distribution System. Tech. rep., Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport
Chao IM (2002) A tabu search method for the truck and trailer routing problem. Comput Oper Res 29:33–51
Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12:568–581
Contardo C, Hemmelmayr V, Crainic TG (2012) Lower and Upper Bounds for The Two-echelon Capacitated Location-Routing Problem. Comput Oper Res 39:3185–3199
Crainic TG, Mancini S, Perboli G, Tadei R (2011) Multi-start Heuristics for The Two-echelon Vehicle Routing Problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6622 LNCS, pp 179–190
Crainic TG, Mancini S, Perboli G, Tadei R (2012) Impact of Generalized Travel Costs on Satellite Location In The Two-echelon Vehicle Routing Problem. Procedia - Soc Behav Sci 39:195–204
Cuda R, Guastaroba G, Speranza MG (2015) A Survey on Two-echelon Routing Problems. Comput Oper Res 55:185–199
Czyzyk J, Mesnier MP, Morė JJ (1998) The neos server. IEEE J Comput Sci Eng 5:68–75
Demir E, Bektaş T, Laporte G (2011) A comparative analysis of several vehicle emission models for road freight transportation. Transp Res Part D: Transp Environ 16:347–357
Demir E, Bektaş T, Laporte G (2012) An adaptive large neighborhood search heuristic for the Pollution-Routing problem. Eur J Oper Res 223(2):346–359
Demir E, Bektaş T, Laporte G (2014) The Bi-objective Pollution-Routing Problem. Eur J Oper Res 232(3):464–478
Dolan ED (2001) The neos server 4.0 administrative guide Technical memorandum. Mathematics and Computer Science Division, Argonne National Laboratory
Eicher (2018) Technical specifications of Eicher PRO 1049. http://www.eicher.in/etb/uploads/pro-1049.pdf
Escui̇n D, Millȧn C, Larrodė E (2012) Modelization of Time-Dependent urban freight problems by using a multiple number of distribution centers. Netw Spat Econ 12:321–336
Feliu JG, Perboli G, Tadei R, Vigo D (2007) The Two-echelon Capacitated Vehicle Routing Problem. Proceedings of the 22nd European Conference on Operational Research, Prague, pp 1–40
Force (2018) Technical specifications of FORCE TRUMP 40. https://trucks.cardekho.com/en/trucks/force/trump-40/specifications
Franceschetti A, Honhon D, Van Woensel T, Bektas T, Laporte G (2013) The Time-dependent Pollution-Routing Problem. Transp Res Part B: Methodol 56:265–293
Gropp W, Morė JJ (1997) Optimization environments and the neos server. In: Buhman MD, Iserles A (eds) Approximation theory and optimization. Cambridge University Press, pp 167–182
Hemmelmayr VC, Cordeau JF, Crainic TG (2012) An Adaptive Large Neighborhood Search Heuristic for Two-echelon Vehicle Routing Problems Arising In City Logistics. Comput Oper Res 39:3215–3228
Jacobsen S, Madsen O (1980) A Comparative Study of Heuristics for a Two-level Routing-location Problem. Eur J Oper Res 5(6):378–387
Jepsen M, Spoorendonk S, Ropke S (2013) A Branch-and-cut Algorithm for The Symmetric Two-echelon Capacitated Vehicle Routing Problem. Transp Sci 47 (1):23–37
Kancharla SR, Ramadurai G (2018) Incorporating driving cycle based fuel consumption estimation in green vehicle routing problems. Sustain Cities Soc 40:214–221
Lin SW, Yu VF, Chou SY (2009) Solving the truck and trailer routing problem based on a simulated annealing heuristic. Comput Oper Res 36:1683–1692
Lin SW, Yu VF, Chou SY (2010) A note on the truck and trailer routing problem. Expert Syst Appl 37:899–903
Lin SW, Yu VF, Lu CC (2011) A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Syst Appl 38:15244–15252
Meihua W, Xuhong T, Shan C, Shumin W (2011) Hybrid ant colony optimization algorithm for two echelon vehicle routing problem. Procedia Eng 15:3361–3365
Mirmohammadsadeghi S, Ahmed S (2015) Memetic heuristic approach for solving truck and trailer routing problems with stochastic demands and time windows. Netw Spatial Econ 15:1093–1115
MORTH (2015) Tech. rep. Ministry of Road Transport & Highways, Transport Research Wing, Government of India
Nagy G, Salhi S (1996) Nested heuristic methods for the location-routing problem. J Oper Res Soc 47:1166–1174
Nguyen VP, Prins C, Prodhon C (2012a) A Multi-start Iterated Local Search With Tabu List and Path Relinking for The Two-echelon Location-Routing Problem. Eng Appl Artif Intell 25:56–71
Nguyen VP, Prins C, Prodhon C (2012b) Solving The Two-echelon Location Routing Problem By a Grasp Reinforced By a Learning Process and Path Relinking. Eur J Oper Res 216:113–126
Perboli G, Tadei R, Tadei R (2010) New Families of Valid Inequalities for The Two-echelon Vehicle Routing Problem. Electron Notes Discret Math 36:639–646
Perboli G, Tadei R, Vigo D (2011) The Two-echelon Capacitated Vehicle Routing Problem: Models and Math-based Heuristics. Transp Sci 45(3):364–380
Renaud J, Boctor FF (2002) A Sweep-based Algorithm for The Fleet Size and Mix Vehicle Routing Problem. Eur J Oper Res 140:618–628
Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40:455–472
Sahin B, Yilmaz H, Ust Y, Guneri AF, Gulsun B (2009) An approach for analysing transportation costs and a case study. Eur J Oper Res 193(1):1–11
Scheuerer S (2006) A tabu search heuristic for the truck and trailer routing problem. Comput Oper Res 33:894–909
Schwengerer M, Pirkwieser S, Raidl GR (2012) A Variable Neighborhood Search Approach for The Two-echelon Location-Routing Problem. In: Evolutionary Computation in Combinatorial Optimization: 12th European Conference, EvoCOP 2012, Malaga, 2012. Proceedings. Springer, Berlin, pp 13–24
Semet F, Taillard E (1993) Solving Real-life Vehicle Routing Problems Efficiently Using Tabu Search. Ann Oper Res 41:469–488
Soysal M, M.bloemhof-ruwaard J, bektaş T (2015) The Time-dependent Two-echelon Capacitated Vehicle Routing Problem With Environmental Considerations. Int J Prod Econ 164:366–378
TATA (2018) Technical specifications of TATA LPT 1613. http://tatatrucks.tatamotors.com/downloads/pdf/lpt-16-2t-gvw-bs-4.pdf
Toyoglu H, Karasan OE, Kara BY (2012) A new formulation approach for Location-Routing problems. Netw Spatial Econ 12:635–659
Tuzun D, Burke LI (1999) A Two-phase Tabu Search Approach to The Location Routing Problem. Eur J Oper Res 116:87–99
USEPA (2017) Dynamometer Drive Schedules. https://www.epa.gov/vehicle-and-fuel-emissions-testing/dynamometer-drive-schedules
Villegas JG, Prins C, Prodhon C, Medaglia AL, Velasco N (2011) A grasp with evolutionary path relinking for the truck and trailer routing problem. Comput Oper Res 38:1319–1334
WHO (2016) Air Pollution Levels Rising In Many of The World’s Poorest Cities. http://www.who.int/mediacentre/news/releases/2016/air-pollution-rising/en/
WHO (2018) WHO ambient (outdoor) air quality database Summary results, update 2018. Technical Report
Acknowledgments
The initial ideas for this paper took shape when the first author was visiting Prof. Russell Thompson at the University of Melbourne. The authors thank the Volvo Research and Education Foundations (VREF) and Center of Excellence for Sustainable Urban Freight Systems (CoE-SUFS) for supporting the visit.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Kancharla, S.R., Ramadurai, G. Multi-depot Two-Echelon Fuel Minimizing Routing Problem with Heterogeneous Fleets: Model and Heuristic. Netw Spat Econ 19, 969–1005 (2019). https://doi.org/10.1007/s11067-018-9437-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11067-018-9437-7