Seminaire LIA: Variants of The Multi-Agent Traveling Salesman Problem with Parking Constraints

Speaker : Cyril Sahuc
Title : Variants of The Multi-Agent Traveling Salesman Problem with Parking Constraints
Abstract : 
The final objective of our project is to optimize the layout of a commercial district by minimizing the overall cost of access to different stores.
We want to achieve this by working on three levers:
- Store's location
- Parking's location and capacity
- (Road's layout)
The model describing a specific situation is as follow:
- Multiple agents must reach one or more stores.
- There is a road network and a pedestrian network.
- Agents enter and leave the system by the road network.
- Parkings are bridges between the two networks.
- To leave the pedestrian network, agents must go back to the parking where they entered.
Minimizing the cost for each agent in this model is a problem rather close to the Traveling Salesman Problem.
We name this problem the MA-TSP-PC: Multi-Agent Traveling Salesman Problem with Parking Constraints.
The main difference with the TSP is the additional constraint that agents must enter and exit the pedestrian network by the same bridge (parking).
Several linear models have been created and tested under CPLEX in order to be able to respect these constraints.
Jeudi, 22 Juin, 2017 - 11:30 to 12:30

Laboratoire Informatique d'Avignon

Université d'Avignon et des Pays de Vaucluse
339 chemin des Meinajaries, Agroparc BP 91228, 84911 Avignon cedex 9
+33 (0)4 90 84 35 00