Séminaire conjoint CRT-Chaire de recherche du Canada en distributique

TITRE: Algorithms for real-time fleet management

CONFÉRENCIER: Frédéric Semet, LAMIH-ROI, Université de Valenciennes et du Hainaut-Cambrésis

DATE et ENDROIT: Mercredi 12 novembre, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE: Jean-François Cordeau (340-6278)

RÉSUMÉ: We address the management in real-time of a fleet of trucks by a carrier. Decisions arise at two different levels. At the planning level, the decisions relate to a static vehicle routing problem in which known transportation requests have to be assigned to trucks in order to minimize the total transportation costs. At the operational level, the real-time decisions are based on the impact of the assignment of new incoming requests. Once the requests have been accepted, a static routing problem is solved to generate an updated assignment. The static problem is a pick-up and delivery vehicle routing problem with time-windows (VRPPDTW) defined on a set of requests and on a fixed size fleet of m trucks. A transportation request is characterized by the pick-up and delivery locations with their associated time-windows, by its volume and by its weight. A truck is characterized by its volume capacity, by its carrying capacity, by its starting and ending locations. The vehicle routing problem consists of determining a set of m vehicle routes of minimum total cost satisfying the following constraints: i) there are at most m vehicle routes and each of them starts and ends at given locations; ii) each request must be assigned; iii) the volume capacity and the carrying capacity for each vehicle must be respected; iv) pick-up and delivery locations must be visited within their time-windows. In this talk, we present the architecture of the optimization module for the management of the fleet in real-time. It involves two types of algorithms. First, a fast path algorithm is invoked to update the cost matrix when a new request is received. Its efficiency is measured through computational experiments on a geographical database. Second, we describe a tabu search algorithm able to provide solutions of the static VRPPDTW in short computation times. Computational results on classical benchmarks are provided. To conclude, we show how this tabu search approach can be adapted to take into account the real-time dimension.