Jacobsen-Grocott 2017 Evolving heuristics for dynamic vehicle routing with.pdf (334.19 kB)

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

Download (334.19 kB)
conference contribution
posted on 31.03.2021, 02:44 by Josiah Jacobsen-Grocott, Yi Mei, Gang Chen, Mengjie Zhang
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 heuristics. © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

History

Preferred citation

Jacobsen-Grocott, J., Mei, Y., Chen, G. & Zhang, M. (2017, January). Evolving heuristics for Dynamic Vehicle Routing with Time Windows using genetic programming. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC) 2017 IEEE Congress on Evolutionary Computation (CEC), IEEE (pp. 1948-1955). IEEE. https://doi.org/10.1109/CEC.2017.7969539

Conference name

2017 IEEE Congress on Evolutionary Computation (CEC)

Conference Place

IEEE

Conference start date

05/06/2017

Conference finish date

08/06/2017

Title of proceedings

Proceedings of the IEEE Congress on Evolutionary Computation (CEC)

Series

IEEE Congress on Evolutionary Computation

Contribution type

Published Paper

Publication or Presentation Year

01/01/2017

Pagination

1948-1955

Publisher

IEEE

Publication status

Published