An Efficient Route Evaluation Method for the Vehicle Routing Problem with Linear Constraints

The vehicle routing problem is the problem of minimizing the traveling distance of vehicles under the condition that every customer must be serviced by a vehicle. In some cases, a solution consists of not only vehicle routes but also the schedules of the vehicles along the routes. The scheduling problem for a vehicle route can often be formulated as a linear programming problem. In this paper, we propose the vehicle routing problem with linear constraints that a vehicle route can be evaluated as a linear programming problem. Many heuristic algorithms for vehicle routing problems use local search methods and the 2-opt* neighborhood, the cross exchange neighborhood and the Or-opt neighborhood are often used. We call them the standard neighborhoods. In this paper, we propose an efficient evaluation method for those neighborhoods for the vehicle routing problem with linear constraints. The computational results for randomly generated instances showed the effect of the proposed method.