Vehicle routing in containers pickup up and delivery processes

The routing problems studied here arise in ISO container distribution and collecting processes, in regions which are oriented to container sea ports or inland terminals. Containers of different sizes, but mostly 20 ft, and 40 ft empty and/or loaded should be delivered to, or collected from the customers. Therefore, the problem studied here is closely related to the vehicle routing problem with backhauls (VRPB) that finds an optimal set of orders (or routes) visiting deliveries (linehauls) and pickups (backhauls). The specificity of the routing problem analyzed here lies in the fact that a truck may simultaneously carry one 40 ft, or two 20 ft containers, using an appropriate trailer type. This means that in one route two, three or four nodes, can be visited, which is equivalent to the problem of matching pickup and delivery nodes in single routes which provide a total travel distance shorter than in the case when nodes are visited separately. In this paper we formulate the problem of matching customer nodes in the container distribution and collecting processes as multiple matching IP, and for the problems of larger sizes we propose a heuristic approach based on matching utilities. The both of proposed approaches are tested on numerical examples.