Abstract: Open vehicle routing problem of multiple distribution centers with simultaneous deliveries and pickups is studied, in which the number and working time of the vehicles are limited. Based on the minimum number and travel distance of vehicles, a multi-objective model is proposed. A novel mixed algorithm based on lagrangian relaxation technique and tabu search algorithm is given, which obtains the maximum lower bound of the optimal solution and then adopts the strategy of assignment and adjustment for clients to achieve the feasible solution. For the tabu search algorithm, a random neighborhood ordering and perturbation mechanisms based on four neighborhood search methods are employed. Computational results show that this algorithm is effective to search the satisfactory solutions and the open collaborative arrangement of vehicle routing is more economic and reasonable than the close independent arrangement of vehicle routing.

Key words: vehicle routing problem, simultaneous deliveries and pickups, model and algorithm