An Effective Iterated Greedy Algorithm for Online Route Planning Problem

Abstract

Route planning serves as the most fundamental part in modern food ordering and delivery system, which is also a classical combinatorial optimization problem. In this paper, we study an online extension of traditional route planning problem where a near-optimal solution has to be generated in a very short time. A simple and effective iterated greedy algorithm is presented along with problem-specific initialization rules, destruction procedure and construction procedure. We also propose a local search method, consisting of two adjustment operators and two neighborhood search operators. With experimental results, we show that our algorithm outperforms the compared evolutionary algorithms and has the capability of providing high-quality solutions within milliseconds.