- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
Column Generation-based Heuristics for Vehicle Routing Problem with Soft Time Windows
-
- QURESHI Ali Gul
- Graduate School of Engineering, Kyoto University
-
- TANIGUCHI Eiichi
- Graduate School of Engineering, Kyoto University
-
- YAMADA Tadashi
- Graduate School of Engineering, Kyoto University
Description
This paper presents a column generation-based heuristics for the Vehicle Routing and scheduling Problem with Soft Time Windows (VRPSTW). The subproblem has been solved using a modified stochastic push forward insertion heuristics that incorporates the early and late arrival penalties. The useful dual information (shadow prices) from the column generation master problem guides the heuristic subproblem to provide negative reduced cost columns of sufficient quality. The performance of column generation-based heuristics is evaluated comparing its results with a genetic algorithms heuristics whose initial population is based on the same insertion heuristics as used in the column generation subproblem. The results showed that the column generation-based heuristics produced better quality solutions, both in terms of cost and environment (CO2), in most cases in only quarter of the computation time, on average.
Journal
-
- Journal of the Eastern Asia Society for Transportation Studies
-
Journal of the Eastern Asia Society for Transportation Studies 8 (0), 827-841, 2010
Eastern Asia Society for Transportation Studies
- Tweet
Details 詳細情報について
-
- CRID
- 1390001205291234176
-
- NII Article ID
- 130000400980
-
- ISSN
- 18811124
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- CiNii Articles
-
- Abstract License Flag
- Disallowed