Evolving heuristics for Dynamic Vehicle Routing with Time Windows using genetic programming

Created by W.Langdon from gp-bibliography.bib Revision:1.3872

  author =       "Josiah Jacobsen-Grocott and Yi Mei and Gang Chen and 
                 Mengjie Zhang",
  booktitle =    "2017 IEEE Congress on Evolutionary Computation (CEC)",
  title =        "Evolving heuristics for Dynamic Vehicle Routing with
                 Time Windows using genetic programming",
  year =         "2017",
  editor =       "Jose A. Lozano",
  pages =        "1948--1955",
  address =      "Donostia, San Sebastian, Spain",
  publisher =    "IEEE",
  isbn13 =       "978-1-5090-4601-0",
  abstract =     "Dynamic vehicle routing problem with time windows is
                 an important combinatorial optimisation problem in many
                 real-world applications. The most challenging part of
                 the problem is to make real-time decisions (i.e.
                 whether to accept the newly arrived service requests or
                 not) during the execution of the routes. It is hardly
                 applicable to use the optimisation methods such as
                 mathematical programming and evolutionary algorithms
                 that are competitive for static problems, since they
                 are usually time-consuming, and cannot give real-time
                 responses. In this paper, we consider solving this
                 problem using heuristics. A heuristic gradually builds
                 a solution by adding the requests to the end of the
                 route one by one. This way, it can take advantage of
                 the latest information when making the next decision,
                 and give immediate response. In this paper, we propose
                 a meta-algorithm to generate a solution given any
                 heuristic. The meta-algorithm maintains a set of routes
                 throughout the scheduling horizon. Whenever a new
                 request arrives, it tries to re-generate new routes to
                 include the new request by the heuristic. It accepts
                 the new request if successful, and reject otherwise.
                 Then we manually designed several heuristics, and
                 proposed a genetic programming-based hyper-heuristic to
                 automatically evolve heuristics. The results showed
                 that the heuristics evolved by genetic programming
                 significantly outperformed the manually designed
  keywords =     "genetic algorithms, genetic programming, combinatorial
                 mathematics, mathematical programming, scheduling,
                 vehicle routing, combinatorial optimisation problem,
                 dynamic vehicle routing problem, evolutionary
                 algorithms, evolving heuristics, genetic
                 programming-based hyper-heuristic, manually designed
                 heuristics, meta-algorithm, optimisation methods,
                 scheduling horizon, static problems, time windows,
                 Optimization, Real-time systems, Time factors, Vehicle
  isbn13 =       "978-1-5090-4601-0",
  DOI =          "doi:10.1109/CEC.2017.7969539",
  month =        "5-8 " # jun,
  notes =        "IEEE Catalog Number: CFP17ICE-ART Also known as

Genetic Programming entries for Josiah Jacobsen-Grocott Yi Mei Gang Chen Mengjie Zhang