A greedy heuristic and a lower bound on a nonlinear stochastic TSP with partially satisfied node demand coverage constraint
International Journal of Mathematics in Operational Research, cilt.26, sa.3, ss.308-326, 2023 (Scopus)
- 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.