A Convex Hull Cheapest Insertion Heuristic for Precedence Constrained Traveling Salesperson Problems or Sequential Ordering Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911799840866304 |
|---|---|
| author | Goutham, Mithun Stockar, Stephanie |
| author_facet | Goutham, Mithun Stockar, Stephanie |
| contents | The convex hull cheapest insertion heuristic is a well-known method that efficiently generates good solutions to the Traveling Salesperson Problem. However, this heuristic has not been adapted to account for precedence constraints that restrict the order in which locations can be visited. Such constraints result in the precedence constrained traveling salesperson problem or the sequential ordering problem, which are commonly encountered in applications where items have to be picked up before they are delivered. In this paper, we present an adapted version of this heuristic that accounts for precedence constraints in the problem definition. This algorithm is compared with the widely used Nearest Neighbor heuristic on the TSPLIB benchmark data with added precedence constraints. It is seen that the proposed algorithm is particularly well suited to cases where delivery nodes are centrally positioned, with pickup nodes located in the periphery, outperforming the Nearest Neighbor algorithm in 97\% of the examined instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_05333 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Convex Hull Cheapest Insertion Heuristic for Precedence Constrained Traveling Salesperson Problems or Sequential Ordering Problems Goutham, Mithun Stockar, Stephanie Robotics Systems and Control Optimization and Control The convex hull cheapest insertion heuristic is a well-known method that efficiently generates good solutions to the Traveling Salesperson Problem. However, this heuristic has not been adapted to account for precedence constraints that restrict the order in which locations can be visited. Such constraints result in the precedence constrained traveling salesperson problem or the sequential ordering problem, which are commonly encountered in applications where items have to be picked up before they are delivered. In this paper, we present an adapted version of this heuristic that accounts for precedence constraints in the problem definition. This algorithm is compared with the widely used Nearest Neighbor heuristic on the TSPLIB benchmark data with added precedence constraints. It is seen that the proposed algorithm is particularly well suited to cases where delivery nodes are centrally positioned, with pickup nodes located in the periphery, outperforming the Nearest Neighbor algorithm in 97\% of the examined instances. |
| title | A Convex Hull Cheapest Insertion Heuristic for Precedence Constrained Traveling Salesperson Problems or Sequential Ordering Problems |
| topic | Robotics Systems and Control Optimization and Control |
| url | https://arxiv.org/abs/2303.05333 |