3 Presentations

• 
  04:00 PM - 04:30 PM

  Branch-Cut-and-Price for the Pickup and Delivery Problem with Time Windows and LIFO Loading

  • Marilène Cherkesly, presenter, GERAD - Polytechnique Montréal
  • Gilbert Laporte, HEC Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  In this presentation, we focus on the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading (PDPTWL). LIFO loading ensures that no handling is required while unloading objects from the vehicle: a linear stack loading structure is assured and an object can only be delivered if it is the one closest to the door. To solve this problem, we propose three exact branch-cut-and-price algorithms. The first algorithm incorporates the LIFO constraints in the master problem. The second algorithm handles the LIFO constraints directly in the shortest path subproblem. To solve it, a dynamic programming algorithm relying on an ad hoc dominance criterion is developed. The third algorithm is a hybrid between the first two methods. We adapt known valid inequalities to the PDPTWL and study the impact of different path relaxations on the total computation time. Computational results will be presented.

• 
  04:30 PM - 05:00 PM

  The Quadratic Capacitated Vehicle Routing Problem

  • Claudio Contardo, GERAD - ESG UQÀM
  • Rafael Martinelli, presenter, GERAD - Polytechnique Montréal

  In this presentation we introduce the Quadratic Capacitated Vehicle Routing Problem (QCVRP), a combinatorial optimization problem that arises in practical applications in logistics and transportation. The QCVRP generalizes other two known problems, the Capacitated Vehicle Routing Problem (CVRP) and the Quadratic Symmetric Traveling Salesman Problem (QSTSP), the former by considering a modified cost matrix in which traveling costs are now associated to pairs of two consecutive edges, and the latter by introducing customer demands and vehicle capacities. We present a three-index vehicle-flow formulation for the problem in which variables represent q-edges (pairs of consecutive edges), and strengthen it with several classes of valid inequalities. We present efficient separation routines for the inequalities used and derive an exact solver based on the branch-and-cut paradigm. We have conducted some preliminary computational experiments to show the efficiency of the modeling and solution approaches. We show that small- and medium-sized problems can be solved to optimality in reasonable computing times.

• 
  05:00 PM - 05:30 PM

  Optimized Target Level - A New Policy for Vendor-Managed Inventory Systems

  • Leandro C. Coelho, presenter, Université Laval
  • Gilbert Laporte, HEC Montréal

  In Vendor-Managed Inventory (VMI) systems, the supplier is responsible not only for delivering the products and routing its vehicles to serve its customers, but also for determining when and how much to deliver to them. The combined optimization of inventory control and vehicle routing gives rise to the Inventory-Routing problem (IRP).

  In the IRP literature, two inventory replenishment policies are traditionally used. The first one, called maximum level (ML), gives full flexibility to the supplier to the supplier to deliver any quantity as long as it respects customer inventory capacities. The other policy, which is much more constrained, is called order-up-to (OU). Under an OU policy, whenever a customer is visited, its inventory level is brought up to its maximum capacity.

  Our objective is to propose a new tactical replenishment policy that would combine the customer-related advantages of OU and the supplier-related benefit of ML which affords more flexibility and lower system costs. This new policy, which we call optimized target level (OTL), determines an optimal replenishment target level for each customer. It can be viewed as an optimized OU policy, except that instead replenishing up to the customer’s capacity, the supplier fills the customer’s inventory up to an OTL. In order to take advantage of this new idea, the OTL of each customer is computed simultaneously with the remaining routing and inventory decisions, in order to jointly optimize the inventory holding costs and the routing costs.

  We perform a computational evaluation of this new policy against both traditional strategies on benchmark instances. We show that it yields lower costs and inventory levels than the OU policy, and is only marginally more expensive than the ML policy, while being easier to implement.