EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2371. Travel and Modify: Travelling Salesmen Problem in Environments Altered by the Salesman

Invited abstract in session MD-58: Real-Life Applications in Routing, stream VeRoLog - Vehicle Routing and Logistics.

Monday, 14:30-16:00
Room: S07 (building: 101)

Authors (first author is the speaker)

1. David Woller
Czech Technical University in Prague
2. Miroslav Kulich
Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague

Abstract

The presented work is inspired by a real-world application in autonomous open pit mining. A drill rig is tasked with digging a large number of blast holes, organized in a tight semi-regular pattern. Digging each hole generates a pile of excess material, that represents a new obstacle for the drill rig. The goal is to determine the piles placement and drill all holes, while minimizing total distance traveled, avoiding all already placed obstacles and getting stuck between them.
We propose the concept of self-deleting graphs, where visiting a vertex causes deletion of a predefined set of edges. This formalism can capture the dynamic addition of obstacles in the motivating application, which is dependent on the previous drill rig path. On these graphs, we formulate variants of the classical Hamiltonian Cycle Problem and Traveling Salesman Problem and design novel solvers for these problems, both exact and heuristic.
In the next step, we address the problem of pile placement in a close vicinity of each hole, given a fixed tour. We formulate the problem as Path-Conforming Circle Placement Problem, propose a heuristic solver and derive solution bounds.
Finally, we combine both problems together and fully address the original application as the Traveling Salesman Problem with Circle Placement, which we solve by combining the already developed approaches. The resulting solver is evaluated on several newly created datasets mimicking the real-world applications.

Keywords

Status: accepted


Back to the list of papers