- #1
Francis
- 2
- 1
- TL;DR
- Hi fellas, I am currently doing solving the aircraft recovery problem using constraint satisfaction programming. To recover some flight schedules from disruption (flight delay or cancellation), it is possible to obtain optimal solutions because the search space is 10^5, however for some the search space can be 10^12. to solve the latter I decompose the search space to find partial solutions. Instead of decomposing, I would like to use a quantum algorithm.
The Aircraft Recovery Problem: consists of finding solutions for a disrupted aircraft flight schedule such that a set of constraints is satisfied, namely continuity, turn-round time, scheduled maintenance, and airport departure/arrival capacity. My approach consists of finding the domains for each flight of the flight schedule while complying with airport capacity. The encoding of this set consists of a set of dictionaries {flight1:[timeSlot11, timeSlot12, ... timeSlot1N], {flight2:[timeSlot21, timeSlot22, ... timeSlot2N] etc.
The search space consists of a matrix that results from the cartesian product of every time slot vector: [timeSlot11, timeSlot12, ... timeSlot1N] ⋅ [timeSlot21, timeSlot22, ... timeSlot2N] ⋅ [timeSlot31, timeSlot32, ... timeSlot3N]... [timeSlotM1, timeSlotM2, ... timeSlotMN]
The number of rows of the matrix is the product of each vector's size.
The algorithm loops through all the rows of the matrix and checks if a row complies with the constraints. If it does and the solution is better the algorithm accepts it.
How would a quantum algorithm be able to speed up this process? Which quantum algorithm? Can you provide me some references?
Please let me know if there is any further information you would like me to provide. Thanks in advance.
The search space consists of a matrix that results from the cartesian product of every time slot vector: [timeSlot11, timeSlot12, ... timeSlot1N] ⋅ [timeSlot21, timeSlot22, ... timeSlot2N] ⋅ [timeSlot31, timeSlot32, ... timeSlot3N]... [timeSlotM1, timeSlotM2, ... timeSlotMN]
The number of rows of the matrix is the product of each vector's size.
The algorithm loops through all the rows of the matrix and checks if a row complies with the constraints. If it does and the solution is better the algorithm accepts it.
How would a quantum algorithm be able to speed up this process? Which quantum algorithm? Can you provide me some references?
Please let me know if there is any further information you would like me to provide. Thanks in advance.