An Exact A<inline-formula> <tex-math notation="LaTeX">$^{*}$</tex-math> </inline-formula>-Based Tree Search Algorithm for TSP With Sequence-and-Load Dependent Risk

Hyungjoo Cha, Chanho Lee, Chi Xie, Qing Chang Lu, Joonyup Eun, Taesu Cheong

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)1-18
Number of pages18
JournalIEEE Transactions on Intelligent Transportation Systems
DOIs
Publication statusAccepted/In press - 2024

Bibliographical note

Publisher Copyright:
IEEE

Keywords

  • Hazardous material delivery
  • iterative deepening A*
  • traveling salesman problem

ASJC Scopus subject areas

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'An Exact A<inline-formula> <tex-math notation="LaTeX">$^{*}$</tex-math> </inline-formula>-Based Tree Search Algorithm for TSP With Sequence-and-Load Dependent Risk'. Together they form a unique fingerprint.

Cite this