×

A biased-randomized discrete-event heuristic for coordinated multi-vehicle container transport across interconnected networks. (English) Zbl 1507.90020

Summary: Modern transport systems are not only large-scale but also highly dynamic, which makes it difficult to optimize by just employing classical methods. This paper analyzes a realistic and novel problem within the Physical Internet initiative which consists of container transportation throughout a spoke-hub network. Containers need to be transported from their origin locations to their final destinations on or before a given deadline, and they can be temporarily stored in network hubs. Each truck can move one container at a time from one hub to another, containers can be transported by different trucks during their path from their origin to their destination, and drivers need to be back at their starting points in due time. A deterministic heuristic, based on discrete-event simulation, is proposed as a first step to address the intrinsic dynamism of this time-evolving system. Then, in a second step, a biased-randomized version of this heuristic is incorporated into a multi-start framework (BR-MS) to generate better solutions. Next, our methodology is extended to a iterated local search (ILS) framework. Finally, a two-stage algorithm, combining both the BR-MS and the ILS frameworks is proposed. Several computational experiments have been carried out on a set of new benchmark instances, adapted from real road networks, to illustrate the problem and compare the performance of the different solving approaches.

MSC:

90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming

Software:

Algorithm 97
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnau, Q.; Juan, A. A.; Serra, I., On the use of learnheuristics in vehicle routing optimization problems with dynamic inputs, Algorithms, 11, 12, 208 (2018) · Zbl 1461.90008
[2] Bayliss, C.; Juan, A. A.; Currie, C. S.; Panadero, J., A learnheuristic approach for the team orienteering problem with aerial drone motion constraints, Applied Soft Computing, 0, 0, 106280 (2020)
[3] Belloso, J.; Juan, A. A.; Faulin, J., An iterative biased-randomized heuristic for the fleet size and mix vehicle-routing problem with backhauls, International Transactions in Operational Research, 26, 1, 289-301 (2019) · Zbl 07765940
[4] Bianchessi, N.; Mansini, R.; Speranza, M. G., A branch-and-cut algorithm for the team orienteering problem, International Transactions in Operational Research, 25, 2, 627-635 (2018) · Zbl 1391.90599
[5] Chambers, M.; Goworowska, J.; Rick, C.; Sedor, J., Freight facts and figures 2015 (2015), U.S. Department of Transportation. Bureau of Transportation Statistics
[6] Chen, X.; Wang, X., Effects of carbon emission reduction policies on transportation mode selections with stochastic demand, Transportation Research Part E: Logistics and Transportation Review, 90, 196-205 (2016)
[7] Chica, M.; Juan, A. A.; Bayliss, C.; Cordón, O.; Kelton, W. D., Why simheuristics? Benefits, limitations, and best practices when combining metaheuristics with simulation, SORT-Statistics and Operations Research Transactions, xx, 311-334 (2020) · Zbl 1472.68181
[8] Costello, B.; Suarez, R., Truck driver shortage analysis 2015, American Trucking Associations, 206, 1-12 (2015)
[9] De Armas, J.; Keenan, P.; Juan, A. A.; McGarraghy, S., Solving large-scale time capacitated arc routing problems: From real-time heuristics to metaheuristics, Annals of Operations Research, 273, 1-2, 135-162 (2019) · Zbl 1411.90342
[10] Díaz, M.; Martín, C.; Rubio, B., State-of-the-art, challenges, and open issues in the integration of internet of things and cloud computing, Journal of Network and Computer Applications, 67, 99-117 (2016)
[11] Dominguez, O.; Juan, A. A.; De La Nuez, I.; Ouelhadj, D., An ILS-biased randomization algorithm for the two-dimensional loading HFVRP with sequential loading and items rotation, Journal of the Operational Research Society, 67, 1, 37-53 (2016)
[12] Dominguez, O.; Juan, A. A.; Faulin, J., A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without item rotations, International Transactions in Operational Research, 21, 3, 375-398 (2014) · Zbl 1291.90034
[13] El-Hajj, R.; Dang, D.-C.; Moukrim, A., Solving the team orienteering problem with cutting planes, Computers and Operations Research, 74, C, 21-30 (2016) · Zbl 1349.90811
[14] Fazili, M.; Venkatadri, U.; Cyrus, P.; Tajbakhsh, M., Physical internet, conventional and hybrid logistic systems: A routing optimisation-based comparison using the eastern canada road network case study, International Journal of Production Research, 55, 9, 2703-2730 (2017)
[15] Ferone, D.; Gruler, A.; Festa, P.; Juan, A. A., Enhancing and extending the classical GRASP framework with biased randomisation and simulation, Journal of the Operational Research Society, 70, 8, 1362-1375 (2019)
[16] Ferone, D.; Hatami, S.; González-Neira, E. M.; Juan, A. A.; Festa, P., A biased-randomized iterated local search for the distributed assembly permutation flow-shop problem, International Transactions in Operational Research, 27, 3, 1368-1391 (2020) · Zbl 07767488
[17] Ferrer, A.; Guimarans, D.; Ramalhinho, H.; Juan, A. A., A BRILS metaheuristic for non-smooth flow-shop problems with failure-risk costs, Expert Systems with Applications, 44, 177-186 (2016)
[18] Fikar, C.; Juan, A. A.; Martinez, E.; Hirsch, P., A discrete-event driven metaheuristic for dynamic home service routing with synchronised trip sharing, European Journal of Industrial Engineering, 10, 3, 323-340 (2016)
[19] Floyd, R. W., Algorithm 97: Shortest path, Communications of the ACM, 5, 6, 345 (1962)
[20] Funke, J.; Kopfer, H., A model for a multi-size inland container transportation problem, Transportation Research Part E: Logistics and Transportation Review, 89, 70-85 (2016)
[21] Gendron, B.; Crainic, T. G.; Frangioni, A., Multicommodity capacitated network design, Telecommunications network planning, 1-19 (1999), Springer
[22] Goel, A., Legal aspects in road transport optimization in europe, Transportation Research Part E: Logistics and Transportation Review, 114, 144-162 (2018)
[23] Goel, A.; Vidal, T.; Kok, A. L., To team up or not: Single versus team driving in european road freight transport, Flexible Services and Manufacturing Journal, xx, x, 1-35 (2020)
[24] Grasas, A.; Juan, A. A.; Faulin, J.; de Armas, J.; Ramalhinho, H., Biased randomization of heuristics using skewed probability distributions: A survey and some applications, Computers & Industrial Engineering, 110, 216-228 (2017)
[25] Gubbi, J.; Buyya, R.; Marusic, S.; Palaniswami, M., Internet of things (IoT): A vision, architectural elements, and future directions, Future Generation Computer Systems, 29, 7, 1645-1660 (2013)
[26] Hakimi, D.; Montreuil, B.; Hajji, A., Simulating physical internet enabled hyperconnected semi-trailer transportation systems, Proceedings of 2nd international physical internet conference, Paris, France (2015)
[27] Hao, C.; Yue, Y., Optimization on combination of transport routes and modes on dynamic programming for a container multimodal transport system, Procedia Engineering, 137, 382-390 (2016)
[28] He, J.; Huang, Y.; Chang, D., Simulation-based heuristic method for container supply chain network optimization, Advanced Engineering Informatics, 29, 3, 339-354 (2015)
[29] Hsu, C.-I.; Hsieh, Y.-P., Routing, ship size, and sailing frequency decision-making for a maritime hub-and-spoke container network, Mathematical and Computer Modelling, 45, 7, 899-916 (2007) · Zbl 1170.90323
[30] Ji, M.; Shen, L.; Shi, B.; Xue, Y.; Wang, F., Routing optimization for multi-type containerships in a hub-and-spoke network, Journal of Traffic and Transportation Engineering, 2, 5, 362-372 (2015)
[31] Ji, M.-J.; Chu, Y.-L., Optimization for hub-and-spoke port logistics network of dynamic hinterland, Physics Procedia, 33, 827-832 (2012)
[32] Juan, A. A.; Faulin, J.; Ferrer, A.; Lourenço, H. R.; Barrios, B., MIRHA: Multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems, Top, 21, 1, 109-132 (2013) · Zbl 1263.90132
[33] Juan, A. A.; Lourenço, H. R.; Mateo, M.; Luo, R.; Castella, Q., Using iterated local search for solving the flow-shop problem: Parallelization, parametrization, and randomization issues, International Transactions in Operational Research, 21, 1, 103-126 (2014) · Zbl 1291.90095
[34] Keenan, P. (2017). TCARP large rural datasets. https://www.researchgate.net/publication/320386608_TCARP_large_rural_datasets. 10.13140/RG.2.2.23723.75043
[35] Kopetz, H., Internet of things, Real-time systems, 307-323 (2011), Springer
[36] Lourenço, H. R.; Martin, O. C.; Stützle, T., Iterated local search: Framework and applications, 363-397 (2010), Springer US: Springer US Boston, MA
[37] Magnanti, T. L.; Wong, R. T., Network design and transportation planning: Models and algorithms, Transportation Science, 18, 1, 1-55 (1984)
[38] Martí, R.; Resende, M. G.; Ribeiro, C. C., Multi-start methods for combinatorial optimization, European Journal of Operational Research, 226, 1, 1-8 (2013) · Zbl 1292.90257
[39] Meller, R. D.; Ellis, K.; Loftis, B., From horizontal collaboration to the physical internet: Quantifying the effects on sustainability and profits when shifting to interconnected logistics systems, Center for Excellence in Logistics and Distribution, University of Arkansas (2012)
[40] Montreuil, B., Toward a physical internet: Meeting the global logistics sustainability grand challenge, Logistics Research, 3, 2-3, 71-87 (2011)
[41] Neves-Moreira, F.; Amorim, P.; Guimarães, L.; Almada-Lobo, B., A long-haul freight transportation problem: Synchronizing resources to deliver requests passing through multiple transshipment locations, European Journal of Operational Research, 248, 2, 487-506 (2016) · Zbl 1346.90159
[42] Pagès-Bernaus, A.; Ramalhinho, H.; Juan, A. A.; Calvet, L., Designing e-commerce supply chains: A stochastic facility-location approach, International Transactions in Operational Research, 26, 2, 507-528 (2019)
[43] Pan, S.; Ballot, E.; Huang, G. Q.; Montreuil, B., Physical internet and interconnected logistics services: Research and applications, International Journal of Production Research, 55, 9, 2603-2609 (2017)
[44] Quintero-Araujo, C. L.; Caballero-Villalobos, J. P.; Juan, A. A.; Montoya-Torres, J. R., A biased-randomized metaheuristic for the capacitated location routing problem, International Transactions in Operational Research, 24, 5, 1079-1098 (2017) · Zbl 1371.90080
[45] Sallez, Y.; Pan, S.; Montreuil, B.; Berger, T.; Ballot, E., On the activeness of intelligent physical internet containers, Computers in Industry, 81, 96-104 (2016)
[46] Sarraj, R.; Ballot, E.; Pan, S.; Hakimi, D.; Montreuil, B., Interconnected logistic networks and protocols: Simulation-based efficiency assessment, International Journal of Production Research, 52, 11, 3185-3208 (2014)
[47] Serrano-Hernández, A.; Juan, A. A.; Faulin, J.; Perez-Bernabeu, E., Horizontal collaboration in freight transport: Concepts, benefits and environmental challenges, SORT-Statistics and Operations Research Transactions, 1, 2, 393-414 (2017) · Zbl 1387.90039
[48] Sohrabi, H.; Montreuil, B.; Klibi, W., Collaborative and hyperconnected distribution systems: A comparative optimization-based assessment, Proceedings of proceedings of the 2016 industrial and systems engineering research conference, Anaheim, CA (2016)
[49] Treiblmaier, H.; Mirkovski, K.; Lowry, P. B.; Zacharia, Z. G., The physical internet as a new supply chain paradigm: A systematic literature review and a comprehensive framework, The International Journal of Logistics Management (2020)
[50] Wang, C.-x., Optimization of hub-and-spoke two-stage logistics network in regional port cluster, Systems Engineering-Theory & Practice, 28, 9, 152-158 (2008)
[51] White, K. P.; Ingalls, R. G., Introduction to simulation, Proceedings of the 2015 winter simulation conference, 1741-1755 (2015), IEEE
[52] Wolfinger, D.; Salazar-González, J.-J., The pickup and delivery problem with split loads and transshipments: A branch-and-cut solution approach, European Journal of Operational Research, 289, 2, 470-484 (2021) · Zbl 1487.90182
[53] Wolfinger, D.; Tricoire, F.; Doerner, K. F., A matheuristic for a multimodal long haul routing problem, EURO Journal on Transportation and Logistics, 8, 4, 397-433 (2019)
[54] Zäpfel, G.; Wasner, M., Planning and optimization of hub-and-spoke transportation networks of cooperative third-party logistics providers, International Journal of Production Economics, 78, 2, 207-220 (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.