Abstract: The problem for urban transport of express is essentially a vehicle routing problem. A mixed-integer programming with the objective of minimum cost is built, which includes the constraints of capacity, time windows, vehicle restriction and it also considers staggering the delivery time. A constructive heuristics is proposed and it takes the distance from one point to the set of points as the priority index for neighborhood search. A column generation algorithm based on pairs of "route-vehicle" is designed and the initial columns are solved by the heuristics. The experimental results show that the approximate optimal solution can be obtained in 175 seconds for the large-scale problem with up to 120 points, which proves the effectiveness of the algorithm and its applicability to VRP for urban transport of express within a certain scale.

Key words: urban transport, vehicle routing problem, heuristics, column generation