Title: A greedy heuristic and a lower bound on a nonlinear stochastic TSP with partially satisfied node demand coverage constraint

Authors: Murat Cal; Senol Altan

Addresses: Department of Engineering Technology, American College of the Middle East, 50000, Egaila Block 6, Ahmadi, Kuwait ' Department of Economics, Faculty of Economics and Administrative Sciences, Haci Bayram Veli University, 06570, Cankaya, Ankara, Turkey

Abstract: The combinatorial travelling salesman problem (TSP) has driven researchers to find faster ways to solve the problem in reasonable times. As a result, researchers modified and created new TSP combinations such as multi-objective TSP or TSP with stochastic constraints. One of these constraints is the node demand coverage constraint. It makes sure that the demand of each node is satisfied in a route. In this study, we re-modify the node demand coverage constraint to be satisfied by some percentage of the time. This approach is more realistic because a node can be visited without covering its demand, allowing the missing of some nodes during the demand covering process while making our model nonlinear. We then provide a greedy heuristic in MATLAB and a lower bound determination procedure for this model and experiment with some predefined datasets.

Keywords: travelling salesman problem; TSP; chance constraints; nonlinear optimisation.

DOI: 10.1504/IJMOR.2023.134835

International Journal of Mathematics in Operational Research, 2023 Vol.26 No.3, pp.308 - 326

Received: 05 Mar 2022
Accepted: 24 Aug 2022
Published online: 14 Nov 2023 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article