An efficient column generation heuristic for vehicle routing with multiple use of vehicles for a rental business
-
- HIROTA Takuya
- Department of Industrial and Management Systems Engineering, School of Creative Science and Engineering, Waseda University
-
- MORITO Susumu
- Department of Industrial and Management Systems Engineering, School of Creative Science and Engineering, Waseda University
-
- HARA Kento
- Department of Industrial and Management Systems Engineering, School of Creative Science and Engineering, Waseda University
Abstract
Optimization of daily vehicle routes with deliveries and pickups as well as multiple use of vehicles for a rental business is considered. The problem is formulated as a variant of generalized set covering problems in which variables correspond to workdays of vehicles. Two variants of column generation heuristic algorithms are developed: one to obtain near-optimal solutions with moderate amount of CPU time together with the associated lower bound, and the other to get solutions with maximum of 8% GAP within 30 CPU seconds. The speed-up of the algorithm is achieved by approximately solving subproblems which exploits information of optimal dual prices associated with the restricted LP master problem. The column generation heuristic algorithms are applied successfully not only to single-depot problems but also to multi-depot problems.
Journal
-
- Journal of Advanced Mechanical Design, Systems, and Manufacturing
-
Journal of Advanced Mechanical Design, Systems, and Manufacturing 10 (3), JAMDSM0050-JAMDSM0050, 2016
The Japan Society of Mechanical Engineers
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1390001205272327040
-
- NII Article ID
- 130005161632
-
- ISSN
- 18813054
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed