Reference : Branch-and-price: principles and its application to a 2-period vehicle routing problem
Scientific conferences in universities or research centers : Scientific conference in universities or research centers
Business & economic sciences : Production, distribution & supply chain management
http://hdl.handle.net/2268/147883
Branch-and-price: principles and its application to a 2-period vehicle routing problem
English
Rezaei Sadrabadi, Mahmood mailto [Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >]
7-Mar-2013
International
Scientific presentation
07/03/2013
Department of Mathematical and Physical Sciences
Newcastle
Australia
[en] Branch-and-price ; vehicle routing problem
[en] We review branch-and-price as an efficient algorithm to solve integer programming problems with huge number of variables. In particular, we discuss column generation algorithm as the main engine in branch-and-price. Implementation of branch-and-price to solve the most basic version of the well-known vehicle routing problem (VRP) is investigated, and some common tricks are introduced. Then, a new extension of VRP is introduced and exploitation of branch-and-price to solve it is discussed. We consider a 2-period vehicle routing problem where each vertex of the network has a positive demand for period 1, 2, or both. Each demand on period 1 can be postponed to period 2 in order to decrease sum of the routing costs on two periods, but it is penalized in the objective function. Similarly, each demand on period 2 can be advanced to period 1, and yet penalized, with the hope of reducing routing costs. We have used many of the classic tricks to implement branch-and-price for solving our 2-period VRP. We have also used new tricks to (1) possibly improve the upper bound during the course of column generation in each node and (2) decrease the computations time to solve pricing problem in column generation.
Researchers ; Students
http://hdl.handle.net/2268/147883

There is no file associated with this reference.

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.