Learning Decision Rules for a Stochastic Multiperiod Capacitated Traveling Salesperson Problem with Irregularly Clustered Customers

Subei Mutailifu, Paolo Brandimarte () and Aili Maimaiti
Additional contact information
Subei Mutailifu: Xinjiang Academy of Transportation Sciences Co., Ltd., Urumqi 830099, China
Paolo Brandimarte: Dipartimento di Scienze Matematiche (DISMA), Politecnico di Torino, 10129 Torino, Italy
Aili Maimaiti: Xinjiang Academy of Transportation Sciences Co., Ltd., Urumqi 830099, China

Logistics, 2025, vol. 9, issue 3, 1-24

Abstract: Background : We consider a variant of the traveling salesperson problem motivated by the case of a company delivering furniture. The problem is both dynamic, due to random arrivals of delivery requests, and multiperiod, due to flexibility in delivering items within a time window of a few days. A sequence of daily routes must be selected over time, and both volume and route duration constraints are relevant. Moreover, customers are irregularly distributed in clusters with high or low density. When receiving a request from a low-density cluster, we may consider the possibility of waiting for further requests from the same cluster, which involves a tradeoff between total traveled distance and service quality. Methods : We designed alternative decision policies based on approximate dynamic programming principles. We compared policy and cost function approximations, tuning their parameters by simulation-based optimization. Results : We compared the decision policies by realistic out-of-sample simulations. A simple trigger-based decision policy was able to achieve a good compromise among possibly conflicting objectives, without resorting to full-fledged multiobjective models. Conclusions : The insights into the relative strengths and weaknesses of the tested policies pave the way to practical extensions. Due to its computational efficiency, the trigger policy may be improved by base-policy rollout and integrated within a multi-vehicle routing architecture.

Keywords: stochastic routing; approximate dynamic programming; policy function approximation; cost function approximation (search for similar items in EconPapers)
JEL-codes: L8 L80 L81 L86 L87 L9 L90 L91 L92 L93 L98 L99 M1 M10 M11 M16 M19 R4 R40 R41 R49 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2305-6290/9/3/119/pdf (application/pdf)
https://www.mdpi.com/2305-6290/9/3/119/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jlogis:v:9:y:2025:i:3:p:119-:d:1727588

Access Statistics for this article

Logistics is currently edited by Ms. Mavis Li

More articles in Logistics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().