A simheuristic algorithm for the stochastic one-commodity pickup and delivery travelling salesman problem

Tejas Ghorpade and Canan G. Corlu

Journal of Simulation, 2023, vol. 17, issue 6, 688-708

Abstract: The one-commodity pickup and delivery traveling salesman problem (1-PDTSP) concerns the transportation of single-type goods that are picked up from supply locations to be delivered to the demand points while minimizing transportation costs. 1-PDTSP finds several applications in practice including the food redistribution operations, where excess edible foods from restaurants and food vendors are collected and delivered to food banks or meal centers, which are then made available to those in need. This paper addresses the realistic case where the pickup and delivery quantities are rarely known in advance and studies the 1-PDTSP with stochastic demand and supply values. We propose a novel simheuristic algorithm, which combines VND metaheuristic with Monte Carlo simulation (SimVND) to solve the stochastic 1-PDTSP. The resulting algorithm takes into account both the transportation cost and the penalty cost, which is incurred due to the inability to satisfy the entire demand. The experimental results indicate that the SimVND solution performs well on deterministic data sets when compared with the existing solutions in the literature. On the stochastic problems, this algorithm leads to a significant decrease in the penalty costs compared to those observed under deterministic solutions. When the penalty costs of not being able to meet demand are high, simheuristic techniques provide a more reliable solution than deterministic heuristic solutions or limited scenario-based solutions.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/17477778.2022.2062261 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjsmxx:v:17:y:2023:i:6:p:688-708

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjsm20

DOI: 10.1080/17477778.2022.2062261

Access Statistics for this article

Journal of Simulation is currently edited by Christine Currie

More articles in Journal of Simulation from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().