Column Generation-based Heuristics for Vehicle Routing Problem with Soft Time Windows

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

Details 詳細情報について

  • CRID
    1390001205291234176
  • NII Article ID
    130000400980
  • DOI
    10.11175/easts.8.827
  • ISSN
    18811124
  • Text Lang
    en
  • Data Source
    • JaLC
    • CiNii Articles
  • Abstract License Flag
    Disallowed

Report a problem

Back to top