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

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

@InProceedings{jacobsen-grocott:2017:CEC,

• author = "Josiah Jacobsen-Grocott and Yi Mei and Gang Chen2 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",
• month = "5-8 " # jun,
• publisher = "IEEE",
• 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 dynamics",
• isbn13 = "978-1-5090-4601-0",
• URL = "https://homepages.ecs.vuw.ac.nz/~yimei/papers/CEC17-Josiah.pdf",
• DOI = "doi:10.1109/CEC.2017.7969539",
• 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 heuristics.",
• notes = "IEEE Catalog Number: CFP17ICE-ART Also known as \cite{7969539}",

}

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

Citations