EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- OR in Mining
- Vehicle Routing
- Dynamical Systems
Status: accepted
Back to the list of papers