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

抄録

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.

収録刊行物

• Proceedings of the Eastern Asia Society for Transportation Studies

  Proceedings of the Eastern Asia Society for Transportation Studies 2009 (0), 151-151, 2009

  Eastern Asia Society for Transportation Studies

キーワード

• City logistics
• Vehicle routing
• Column generation heuristics

詳細情報

• CRID: 1390282680653359872
• NII論文ID: 130005036866
• DOI: 10.11175/eastpro.2009.0.151.0
• 本文言語コード: en
• データソース種別:
  • JaLC
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可