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

TITRE: Shipping Multiple-Items by Capacitated Vehicles - An Optimal Dynamic Programming Approach

CONFÉRENCIER: Shoshana Anily, Tel Aviv University, Tel Aviv, Israel.

DATE et ENDROIT: mercredi 11 septembre, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE: Gilbert Laporte (343-6143)

RÉSUMÉ: We consider a two-echelon system in which multiple-items are transferred from the upper echelon (for example, a warehouse) to the lower echelon (for example, a retailer) through identical capacitated vehicles, or freight wagons. Any mixture of the items may be loaded on a vehicle. The lower echelon is facing dynamic deterministic demand for several items, over a finite planning horizon. A vehicle incurs a fixed cost for each trip made from the upper to the lower echelon. In addition, there exist item dependent variable shipping costs and inventory holding costs at the retailer, which are both constant over time. The objective is to find a shipment schedule that minimizes the total cost, while satisfying demand on time. We address and partially resolve the question regarding the problem's complexity by introducing a dynamic programming algorithm whose complexity is polynomial for a fixed number of items, but exponential otherwise. Our dynamic programming formulation is based on properties satisfied by the optimal solution, and is using an innovative way for partitioning the problem into sub-problems.