An Exact A*-Based Tree Search Algorithm for TSP With Sequence-and-Load Dependent Risk
Authors: 
Hyungjoo Cha, Chanho Lee, Chi Xie, Qing-Chang Lu, Joonyup Eun, Taesu CheongAuthors Info & Claims
Pages 10817 - 10834
Abstract
The hazardous material transportation requires extensive care owing to the disastrous consequences of accidents, such as chemical spills or radioactive exposures. Consequently, a minimum risk delivery plan that is dynamically decided by the cargo load of the vehicle at each customer must be scheduled. We introduce a traveling salesman problem (TSP) with a sequence-and-load dependent risk, which differs from the conventional TSP as the arc costs are determined by the hazardous cargo load at each decision epoch. We define our problem in a dynamic programming formulation and present mixed-integer linear program with a nonlinear objective function. To efficiently retrieve exact optimal solutions, we propose an iterative-deepening A*-based tree search algorithm using admissible lower and efficient upper bound algorithms for guaranteed optimality. Numerical experiments indicate that the proposed algorithm outperforms a current state-of-the-art solver. An ablation study and sensitivity analysis demonstrate the effectiveness of the proposed algorithm and derive managerial insights.
References
[1]
F. M. C. S. Administration, “Comparative risks of hazardous materials and non-hazardous materials truck shipment accidents/incidents,” 2001.
[2]
Y. Akagi, A. Kishimoto, and A. Fukunaga, “On transposition tables for single-agent search and planning: Summary of results,” in Proc. Int. Symp. Combinat. Search, 2010, vol. 1, no. 1, pp. 2–9.
[3]
D. A. Alcantara, V. Volkov, S. Sengupta, M. Mitzenmacher, J. D. Owens, and N. Amenta, “Building an efficient hash table on the GPU,” in GPU Comput. Gems Jade Ed., 2012, pp. 39–53.
[4]
S. Alumur and B. Y. Kara, “A new model for the hazardous waste location-routing problem,” Comput. Oper. Res., vol. 34, no. 5, pp. 1406–1423, May 2007.
[5]
E. Ardjmand, W. A. Young, G. R. Weckman, O. S. Bajgiran, B. Aminipour, and N. Park, “Applying genetic algorithm to a new bi-objective stochastic model for transportation, location, and allocation of hazardous materials,” Expert Syst. Appl., vol. 51, pp. 49–58, Jun. 2016.
[6]
S. Arunapuram, K. Mathur, and D. Solow, “Vehicle routing and scheduling with full truckloads,” Transp. Sci., vol. 37, no. 2, pp. 170–182, May 2003.
[7]
P. Augerat, D. Naddef, J. Belenguer, E. Benavent, A. Corberan, and G. Rinaldi, “Computational results with a branch and cut code for the capacitated vehicle routing problem,” Universite Joseph Fourier, Grenoble, France, Tech. Rep. 949-M, 1998.
[8]
T. Bektaş and G. Laporte, “The pollution-routing problem,” Transp. Res. B, Methodol., vol. 45, no. 8, pp. 1232–1250, Sep. 2011.
[9]
L. Bianco, M. Caramia, and S. Giordani, “A bilevel flow model for hazmat transportation network design,” Transp. Res. Part C, Emerg. Technol., vol. 17, no. 2, pp. 175–196, Apr. 2009.
[10]
A. Bronfman, V. Marianov, G. Paredes-Belmar, and A. Lüer-Villagra, “The maximin HAZMAT routing problem,” Eur. J. Oper. Res., vol. 241, no. 1, pp. 15–27, Feb. 2015.
[11]
K. Bujel, F. Lai, M. Szczecinski, W. So, and M. Fernandez, “Solving high volume capacitated vehicle routing problem with time windows using recursive-DBSCAN clustering algorithm,” 2018, arXiv:1812.02300.
[12]
P. Carotenuto, S. Giordani, S. Ricciardelli, and S. Rismondo, “A Tabu search approach for scheduling hazmat shipments,” Comput. Oper. Res., vol. 34, no. 5, pp. 1328–1350, May 2007.
[13]
G. B. Dantzig, D. R. Fulkerson, and S. M. Johnson, “Solution of a large-scale traveling-salesman problem,” J. Oper. Res. Soc. Amer., vol. 2, no. 4, pp. 393–410, Nov. 1954. 10.1287/opre.2.4.393.
[14]
J. Du, X. Li, L. Yu, R. Dan, and J. Zhou, “Multi-depot vehicle routing problem for hazardous materials transportation: A fuzzy bilevel programming,” Inf. Sci., vol. 399, pp. 201–218, Aug. 2017.
[15]
J. F. Ehmke, A. M. Campbell, and B. W. Thomas, “Vehicle routing to minimize time-dependent emissions in urban areas,” Eur. J. Oper. Res., vol. 251, no. 2, pp. 478–494, Jun. 2016.
[16]
E. Erkut and A. Ingolfsson, “Transport risk models for hazardous materials: Revisited,” Oper. Res. Lett., vol. 33, no. 1, pp. 81–89, Jan. 2005.
[17]
T. Fan, W.-C. Chiang, and R. Russell, “Modeling urban hazmat transportation with road closure consideration,” Transp. Res. Part D, Transp. Environ., vol. 35, pp. 104–115, Mar. 2015.
[18]
M. Fischetti, J. J. Salazar González, and P. Toth, “A branch-and-cut algorithm for the symmetric generalized traveling salesman problem,” Oper. Res., vol. 45, no. 3, pp. 378–394, Jun. 1997.
[19]
M. Flood, “The traveling-salesman problem,” Oper. Res., vol. 4, no. 1, pp. 61–75, Feb. 1956.
[20]
P. Fontaine, “The vehicle routing problem with load-dependent travel times for cargo bicycles,” Eur. J. Oper. Res., vol. 300, no. 3, pp. 1005–1016, Aug. 2022.
[21]
P. Fontaine and S. Minner, “Benders decomposition for the hazmat transport network design problem,” Eur. J. Oper. Res., vol. 267, no. 3, pp. 996–1002, Jun. 2018.
[22]
R. Fukasawaet al., “Robust branch-and-cut-and-price for the capacitated vehicle routing problem,” Math. Program., vol. 106, no. 3, pp. 491–511, May 2006.
[23]
M. R. Future. (2021). Hazardous Goods Logistics Market Size, Share, Growth|report, 2030. Accessed: Jul. 14, 2022. [Online]. Available: https://www.marketresearchfuture.com/reports/dangerous-hazardous-goods-logistics-market-one-10099
[24]
D. Gelperin, “On the optimality of A*,” Artif. Intell., vol. 8, no. 1, pp. 69–76, 1977.
[25]
M. X. Goemans, “Worst-case comparison of valid inequalities for the TSP,” Math. Program., vol. 69, nos. 1–3, pp. 335–349, Jul. 1995.
[26]
(2022). Gurobi Optimizer Reference Manual. [Online]. Available: https://www.gurobi.com
[27]
S. Han, K. Zhu, M. Zhou, and X. Liu, “Joint deployment optimization and flight trajectory planning for UAV assisted IoT data collection: A bilevel optimization approach,” IEEE Trans. Intell. Transp. Syst., vol. 23, no. 11, pp. 21492–21504, Nov. 2022.
[28]
P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. Syst. Sci. Cybern., vol. SCS-4, no. 2, pp. 100–107, Jul. 1968.
[29]
(2022). Hazardous Materials Management (hazmat) | GSA. Accessed: Jul. 5, 2022. [Online]. Available: https://www.gsa.gov/buying-selling/purchasing-programs/requisition-programs/gsa-global-supply/supply-standards/hazardous-materials-management-hazmat
[30]
A. Heimfarth, M. Ostermeier, and A. Hübner, “A mixed truck and robot delivery approach for the daily supply of customers,” Eur. J. Oper. Res., vol. 303, no. 1, pp. 401–421, Nov. 2022.
[31]
M. Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees,” Oper. Res., vol. 18, no. 6, pp. 1138–1162, Dec. 1970. 10.1287/opre.18.6.1138.
[32]
N. Holeczek, “Hazardous materials truck transportation problems: A classification and state of the art literature review,” Transp. Res. D, Transp. Environ., vol. 69, pp. 305–328, Apr. 2019.
[33]
H. Hu, X. Li, Y. Zhang, C. Shang, and S. Zhang, “Multi-objective location-routing model for hazardous material logistics with traffic restriction constraint in inter-city roads,” Comput. Ind. Eng., vol. 128, pp. 861–876, Feb. 2019.
[34]
A. Jabbarzadeh, N. Azad, and M. Verma, “An optimization approach to planning rail hazmat shipments in the presence of random disruptions,” Omega, vol. 96, Oct. 2020, Art. no.
[35]
P. Jiang, J. Men, H. Xu, S. Zheng, Y. Kong, and L. Zhang, “A variable neighborhood search-based hybrid multiobjective evolutionary algorithm for HazMat heterogeneous vehicle routing problem with time windows,” IEEE Syst. J., vol. 14, no. 3, pp. 4344–4355, Sep. 2020.
[36]
S. R. Kancharla and G. Ramadurai, “Electric vehicle routing problem with non-linear charging and load-dependent discharging,” Expert Syst. Appl., vol. 160, Dec. 2020, Art. no.
[37]
R. E. Korf, “Depth-first iterative-deepening: An optimal admissible tree search,” Artif. Intell., vol. 27, pp. 97–109, Sep. 1985.
[38]
R. E. Korf, M. Reid, and S. Edelkamp, “Time complexity of iterative-deepening—A,” Artif. Intell., vol. 129, nos. 1–2, pp. 199–218, Jun. 2001.
[39]
G. Laporte, “Fifty years of vehicle routing,” Transp. Sci., vol. 43, no. 4, pp. 408–416, Nov. 2009.
[40]
C. Lemardelé, M. Estrada, L. Pagès, and M. Bachofner, “Potentialities of drones and ground autonomous delivery devices for last-mile logistics,” Transp. Res. Part E, Logistics Transp. Rev., vol. 149, May 2021, Art. no.
[41]
C. Levins. (2018). How Common Are Shipping Hazmat Spills? By ASC, Inc. Accessed: Jul. 5, 2022. [Online]. Available: https://www.airseacontainers.com/blog/how-common-are-shipping-hazmat-spills
[42]
B. Li, G. Wu, Y. He, M. Fan, and W. Pedrycz, “An overview and experimental study of learning-based optimization algorithms for the vehicle routing problem,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 7, pp. 1115–1138, Jul. 2022.
[43]
Y. Linet al., “A multi-AGV routing planning method based on deep reinforcement learning and recurrent neural network,” IEEE/CAA J. Autom. Sinica, pp. 1–3, 2023. 10.1109/jas.2023.123300.
[44]
C. Ma, J. Zhou, and D. Yang, “Causation analysis of hazardous material road transportation accidents based on the ordered logit regression model,” Int. J. Environ. Res. Public Health, vol. 17, no. 4, p. 1259, Feb. 2020.
[45]
X. Meng, J. Li, M. Zhou, and X. Dai, “A dynamic colored traveling salesman problem with varying edge weights,” IEEE Trans. Intell. Transp. Syst., vol. 23, no. 8, pp. 13549–13558, Aug. 2022.
[46]
C. E. Miller, A. W. Tucker, and R. A. Zemlin, “Integer programming formulation of traveling salesman problems,” J. ACM, vol. 7, no. 4, pp. 326–329, Oct. 1960.
[47]
S. S. Mohri, M. Mohammadi, M. Gendreau, A. Pirayesh, A. Ghasemaghaei, and V. Salehi, “Hazardous material transportation problems: A comprehensive overview of models and solution approaches,” Eur. J. Oper. Res., vol. 302, no. 1, pp. 1–38, Oct. 2022.
[48]
M. Nazarahari, E. Khanmirza, and S. Doostie, “Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm,” Exp. Syst. Appl., vol. 115, pp. 106–120, Jan. 2019.
[49]
M. Nazari, A. Oroojlooy, L. Snyder, and M. Takác, “Reinforcement learning for solving the vehicle routing problem,” in Proc. Adv. Neural Inf. Process. Syst., vol. 31, 2018, pp. 1–12.
[50]
J. Ouenniche, P. K. Ramaswamy, and M. Gendreau, “A dual local search framework for combinatorial optimization problems with TSP application,” J. Oper. Res. Soc., vol. 68, no. 11, pp. 1377–1398, Nov. 2017.
[51]
L. Perron and V. Furnon. (2019). OR-Tools. [Online]. Available: https://developers.google.com/optimization
[52]
R. Pradhananga, E. Taniguchi, and T. Yamada, “Ant colony system based routing and scheduling for hazardous material transportation,” Proc. Social Behav. Sci., vol. 2, no. 3, pp. 6097–6108, 2010.
[53]
A. W. Siddiqui and M. Verma, “A bi-objective approach to routing and scheduling maritime transportation of crude oil,” Transp. Res. Part D, Transp. Environ., vol. 37, pp. 65–78, Jun. 2015.
[54]
G. Tang, C. Tang, C. Claramunt, X. Hu, and P. Zhou, “Geometric A-star algorithm: An improved A-star algorithm for AGV path planning in a port environment,” IEEE Access, vol. 9, pp. 59196–59210, 2021.
[55]
M. Taslimi, R. Batta, and C. Kwon, “Medical waste collection considering transportation and storage risk,” Comput. Oper. Res., vol. 120, Aug. 2020, Art. no.
[56]
G. Van Rossum, The Python Library Reference, Release 3.8.2. Wilmington, DE, USA: Python Software Foundation, 2020.
[57]
N. Wang, M. Zhang, A. Che, and B. Jiang, “Bi-objective vehicle routing for hazardous materials transportation with no vehicles travelling in echelon,” IEEE Trans. Intell. Transp. Syst., vol. 19, no. 6, pp. 1867–1879, Jun. 2018.
[58]
Z. Wang and J.-B. Sheu, “Vehicle routing problem with drones,” Transp. Res. B, Methodol., vol. 122, pp. 350–364, Apr. 2019.
[59]
Y. Wu, W. Song, Z. Cao, J. Zhang, and A. Lim, “Learning improvement heuristics for solving routing problems,” IEEE Trans. Neural Netw. Learn. Syst., vol. 33, no. 9, pp. 5057–5069, Sep. 2022.
[60]
Y. Zhou, W. Xu, Z.-H. Fu, and M. Zhou, “Multi-neighborhood simulated annealing-based iterated local search for colored traveling salesman problems,” IEEE Trans. Intell. Transp. Syst., vol. 23, no. 9, pp. 16072–16082, Sep. 2022.
[61]
X. Xu, J. Li, and M. Zhou, “Delaunay-Triangulation-Based variable neighborhood search to solve large-scale general colored traveling salesman problems,” IEEE Trans. Intell. Transp. Syst., vol. 22, no. 3, pp. 1583–1593, Mar. 2021.
[62]
M. Zhang, N. Wang, Z. He, and B. Jiang, “Vehicle routing optimization for hazmat shipments considering catastrophe avoidance and failed edges,” Transp. Res. Part E, Logistics Transp. Rev., vol. 150, Jun. 2021, Art. no.
[63]
Z. Zhang, H. Liu, M. Zhou, and J. Wang, “Solving dynamic traveling salesman problems with deep reinforcement learning,” IEEE Trans. Neural Netw. Learn. Syst., vol. 34, no. 4, pp. 2119–2132, Apr. 2023.
[64]
X. Xu, J. Li, and M. Zhou, “Bi-objective colored traveling salesman problems,” IEEE Trans. Intell. Transp. Syst., vol. 23, no. 7, pp. 6326–6336, Jul. 2022.
[65]
Z. Zhou, F. Chu, A. Che, and M. Zhou, “ε-constraint and fuzzy logic-based optimization of hazardous material transportation via lane reservation,” IEEE Trans. Intell. Transp. Syst., vol. 14, no. 2, pp. 847–857, Jun. 2013.
[66]
K. G. Zografos and K. N. Androutsopoulos, “A heuristic algorithm for solving hazardous materials distribution problems,” Eur. J. Oper. Res., vol. 152, no. 2, pp. 507–519, Jan. 2004.
Index Terms
- An Exact A*-Based Tree Search Algorithm for TSP With Sequence-and-Load Dependent Risk
Index terms have been assigned to the content through auto-classification.
Recommendations
An Exact Algorithm for the Quadratic Assignment Problem on a Tree
The Tree QAP is a special case of the Quadratic Assignment Problem QAP where the nonzero flows form a tree. No condition is required for the distance matrix. This problem is NP-complete and is also a generalization of the Traveling Salesman Problem. In ...
Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer ScienceWe study the prize-collecting versions of the Steiner tree, traveling salesman, and stroll (a.k.a. Path-TSP) problems (PCST, PCTSP, and PCS, respectively): given a graph (V, E) with costs on each edge and a penalty (a.k.a. prize) on each node, the goal ...
Exact and Approximate Maximum Inner Product Search with LEMP
Invited Paper from ICDT 2014, Invited Paper from EDBT 2015, Regular Papers and Technical CorrespondenceWe study exact and approximate methods for maximum inner product search, a fundamental problem in a number of data mining and information retrieval tasks. We propose the LEMP framework, which supports both exact and approximate search with quality ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1524-9050 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 16 April 2024
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024