An Iterated Local Search Algorithm for Commuting Bus Routing Problem with Latest Arrival Time Constraint

Given a set of bus stops and a set of employees, the commuting bus routing problem with latest arrival time constraint (CBRP-LATC) aims to determine routes of buses to carry every employee from the company to one of the bus stops at which he/she wants to get off. Each employee walks to his/her destination after getting off the bus and has a desired time when he/she wants to arrive there, which is called the latest arrival time. The objective is to find a set of routes with the minimum total traveling cost that covers all employees’ destinations under bus capacity and latest arrival time constraints. We propose an iterated local search algorithm in which we use two kinds of neighborhood operations called set-del/1-ins and VRP-OPT*. The set-del/1ins operation consists of three neighborhood operations, setdel, 1-ins and set-del-ins to remove or assign employees from or to a bus route. The VRP-OPT* is a local search algorithm to improve the distances of routes based on four neighborhood operations, 2-opt, 2-opt*, relocate and cross-exchange. Computational results show the effectiveness of the two neighborhood operations.