EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1848. The shortest path problem with path constraints
Invited abstract in session TC-28: Advancements of OR-analytics in statistics, machine learning and data science 6, stream Advancements of OR-analytics in statistics, machine learning and data science.
Tuesday, 12:30-14:00Room: 065 (building: 208)
Authors (first author is the speaker)
| 1. | Nan Xu
|
| China Southern Airlines Company Limited | |
| 2. | Zhang Miaomiao
|
| Information Center, China Southern Airlines Company Limited | |
| 3. | Yicong Qin
|
| China Southern Airlines | |
| 4. | Hao Zhang
|
| China Southern Airlines |
Abstract
Motivated by the practical aircraft routing problem in civil flight planning, we consider a variant of the shortest path problem with inclusionary and exclusionary constraints, specifying whether node Y must or must not be visited after node X is visited.
The problem is defined on a directed graph G, with a source node S and a sink node T. We introduce an algorithm that generates an augmented graph G’ from the original graph G, ensuring compliance with the inclusionary and exclusionary constraints. This transformation reduces the constrained shortest path problem in G to a classic shortest path problem in the augmented graph G’. For each inclusionary constraint, we modify the original graph to ensure that all paths from X to T pass through Y. For each exclusionary constraint, we modify the original graph so that all paths from X to Y are redirected to a duplicate node Y', which has no outgoing arcs, ensuring that no path extended from X to T through Y/Y’.
It need to be proved that: (1) There are no paths violating the constraints in G’; (2) For each valid path in G, there exists a corresponding path in G’; and (3) For each path in G’, there is a corresponding path in G. We demonstrate the algorithm's validity through proofs by contradiction.
Numerical experiments demonstrate the efficiency of our algorithm. Furthermore, the algorithm has been successfully integrated into our flight planning system, indicating its practical utility.
Keywords
- Airline Applications
- Transportation
- Algorithms
Status: accepted
Back to the list of papers