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

Cal M., Altan S.

International Journal of Mathematics in Operational Research, cilt.26, sa.3, ss.308-326, 2023 (Scopus) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 26 Sayı: 3
  • Basım Tarihi: 2023
  • Doi Numarası: 10.1504/ijmor.2023.134835
  • Dergi Adı: International Journal of Mathematics in Operational Research
  • Derginin Tarandığı İndeksler: Scopus, PASCAL, INSPEC, zbMATH
  • Sayfa Sayıları: ss.308-326
  • Anahtar Kelimeler: chance constraints, nonlinear optimisation, travelling salesman problem, TSP
  • Ankara Hacı Bayram Veli Üniversitesi Adresli: Evet

Özet

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.