Int. Journal of Business Science and Applied Management, Volume 7, Issue 3, 2012

Two mathematical formulations for the containers drayage

problem with time windows

Milorad Vidović

University of Belgrade, Logistics Department, Faculty of Transport and Traffic Engineering

Vojvode Stepe 305, 11000 Belgrade, Serbia

Telephone: +381 011 30 91 300

Email: m.nikolic@sf.bg.ac.rs

Dražen Popović

University of Belgrade, Logistics Department, Faculty of Transport and Traffic Engineering

Vojvode Stepe 305, 11000 Belgrade, Serbia

Telephone: +381 011 30 91 273

Email: d.popovic@sf.bg.ac.rs

Abstract

problem analyzed here lies in the fact that a truck may simultaneously carry one 40ft, or two 20ft 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 nodes in single routes which provide a total travel distance shorter than in

the case when nodes are visited separately. The paper presents two optimal MIP mathematical formulations for

the case when pickup and delivery nodes could be visited only in specific time interals - time windows.

Proposed approaches are tested on numerical examples.

Keywords: containers drayage, pickup delivery, vehicle routing problems with TW

Acknowledgements: This research was partially supported by the Ministry of Education and Science Republic

are delivered by trucks to customers oriented to a container sea port or an inland container terminal. In the

intermodal transportation (Fig. 1a) the major part of the cargo’s journey is performed by rail, inland waterway or

sea, while the initial and/or final legs, distribution and collection of containers, are typically carried out by road

(for more details about intermodal transportation systems see Crainic and Kim, 2007). Truck should deliver a

loaded container that has arrived at an terminal (import i.e. inbound container) to a consignee, and to pickup and

haul back the loaded container from consignor to the terminal (export i.e. outbound container). In the case when

a part of a container terminal serves as an empty containers’ depot, in addition to pickup – delivery operations

with loaded containers, the empty containers also need to be delivered to a shipper for loading and hauled back

empty to the terminal after unloading goods at the consignee site. In addition, when the time of subsequent

shipment and the suitability of an empty container at the consignee site, in terms of type size and ownership, are

imposed by the technology and customers’ requirements. Drayage includes regional movements of loaded and

empty equipment (trailers and containers) by tractors between terminals, shippers, consignees, and equipment

yards. In general, drayage operations involve not only the provision of containers but also empty trailers

(Macharis & Bontekoning, 2004), while in this research only the problem of containers pickup and delivery is

considered.

Figure 1: Intermodal transportation system (1a) and possible types of container moves in container truck

transportation (1b)

the USA and Canada (Nagl, 2007). In conjunction with the length, the weight of container is also very

important. Most countries allow transport of one fully loaded 20ft or 40ft container, but although transport of

two 20ft containers would be possible regarding length, the weight is an obstacle. In most countries transport of

two loaded 20ft containers by a standard vehicle is not permitted, except in the case when the weight limitation

of 26 tons is not exceeded. In the USA, Australia, Canada, Finland and Sweden the vehicles in use are the ones

that offer the possibility of transporting two fully loaded 20ft containers, while the EU has set up regulations

which permit certain types of vehicles called “modular concept vehicles”, offering the possibility of transporting

two fully loaded 20ft containers using special combined chassis. In turn, the use of those technical solutions

provides different opportunities for improving the efficiency of container transportation by merging different

pickup and delivery operations in a single route.

importance in intermodal freight transportation. Jula et al. (2005) formulated the problem of container

movement with time windows at origins and destinations as asymmetric multiple traveling salesman problem

and proposed three solving approaches. Coslovich et al. (2006) investigated a container drayage operation with

the present and future operating costs minimized. Imai et al. (2007) formulated a container drayage problem as a

pickup and delivery and proposed Lagrangian relaxation to solve the problem. Chung et al. (2007) built several

mathematical models of container truck transportation. They formulate the basic problem where every vehicle

can transport exactly one container at a time, and the multi-commodity problem with a combined chassis used in

transporting two 20ft containers or one 40ft container. To solve the problem a solution algorithm based on the

Insertion Heuristic was proposed. Namboothiri and Erera (2008) studied the management of a fleet of trucks

providing container pickup and delivery service (drayage) to a port with an appointment-based access control

Problems with Pickup and Delivery (VRPPD), can be found in recent comprehensive overview given by

Parragh et al. (2008a, 2008b).

The purpose of this paper is to propose mathematical formulations for the optimal trucks’ routing in

containers drayage operations in the case when pickup and delivery nodes may be visited only during a certain

predefined time intervals. In this way, our previous research (Vidović et al. 2011a, Vidović et al. 2011b) has

been extended by introducing additional mathematical formulation based on general mixed integer

programming model for the vehicle routing problem with simultaneous pickups and deliveries (VRP-SPDTW),

proposed by Mingyong and Erbao (2010). Therefore, most of introductionary part remained the same, while as

in previous research, we consider both, empty and loaded containers’ moves in case when combined chassis for

transporting two 20ft containers or one 40ft container are used. Direct moves of empty containers from a

by Imai et al. (2007), to the multi-commodity case. Besides respecting the multi-commodity, this paper also

differs in the overall objective which is to find optimal matching possibilities of nodes that should be merged in

the same route forming backhaul loop. Another characteristic of the proposed formulations is in respecting the

simultaneous pickup and delivery operations.

The remainder of this paper is organized as follows. Section 2 presents two optimal problem formulations.

Section 3 presents computational results, and Section 4 gives some concluding remarks.

2 PROBLEM FORMULATIONS

The problem of distributing – collecting ISO containers (20ft, and 40ft) may be described as a variant of

VRPB in which a truck visits up to four nodes until return to terminal. Loaded containers arrived in terminal

(import i.e. inbound containers), or empty containers from the terminal depot should be delivered to customers,

(2)

(3)

(8)

(9)

Where

p,q,w,e indexes of customer nodes with 20ft containers supply or demand (p,q



z,t indexes of customer nodes with 40ft containers supply or demand (tN40-, zN40+)

i,j,k,l indexes of any arbitrary customer nodes

N

w

,w

respectively

a

,b

interval when the node is available for the servicing

s

,s

t

Objective function (1) tries to minimize total transportation costs of all routes that are used for serving all

of supply/demand nodes by solving the set of nodes matching problems. Terms 1 - 2 of the objective function

(1) define all allowable four, terms 3 – 7 three and terms 8 – 12 all allowable two nodes matchings. Terms 13 –

16 define direct pickup and delivery routes, visiting only one node. Sets of constraint (2) – (5) prohibit multiple

visits of the same node, and provide that each node must be visited exactly once, either in a route visiting four,

three, two or one customer node. Constraints (6) to (9) are time windows constraints which allow node to be

visited only during the interval when the nodes are available for servicing. Constraints (10) to (13) define binary

nature of variables.

Obviously, the idea of defining time windows constraint, in this multiple assignment model formulation, is

that the arbitrary sequence of nodes visited in the same route should satisfy sequence of constraints indicating

vehicle routing problems as special cases, and here is slightly modified and adjusted with the objective to

represent the container drayage problem.

As same as in the previous model, let

containers move requests, and

terminal node, while any customer node may simultaneously have both, containers demand and supply move

requests. The assumption gives again opportunity of transforming graph into the another, in which each

customer node is replaced with task nodes. In this way all task nodes of the transformed graph have single move

Q – vehicle capacity

c

– transport costs between customer nodes i and j

containers ) picked up from the task nodes up to task node i, and transported in arc i,jE

z

– integer variable representing number of containers (TEU) to be delivered after task node i, and

define variables domains.

4 CONCLUDING REMARKS

This paper proposes methods for the optimal trucks’ routing in containers drayage operations. We consider

both, empty and loaded containers’ moves in case when combined chassis for transporting two 20ft containers

or one 40ft container are used. To solve the problem containers’ drayage is formulated as a multiple assignment

problem with time windows, as well as the VRP with simultaneous pickups and deliveries. That is, pickup and

delivery nodes are visited only in specific time intervals.

Preliminary testing of the proposed approaches shows that the first model seems to be very promising, but

Regan (2002), who stated that typical sub-fleet of trucks, consists of less than 20 trucks and is able to handle at

most 75 containers a day.

al. (2007), in our notation corresponds to the combination of two nodes matching and direct routes realization,

and therefore it can be concluded that the container drayage problem considered here is also NP-hard, since one

performances and possible adjustments are without any doubt directions for the very near future, but improving

algorithms with the other real life constraints (nonhomogenous fleet of vehicles, multiple use of vehicles…)

should be an important issue for the future. Also, metaheuristics application is also considered as an important

direction of future research.

Chung, K.H., Ko, C.S., Shin, J.Y., Hwang, H. & Kim, K.H. (2007). Development of mathematical models for

the container road transportation in Korean trucking industries. Computers & Industrial Engineering, 53,

Ileri, Y., Bazaraa, M., Gifford, T., Nemhauser, G., Sokol, J. & Wikum, E. (2006). An Optimization Approach

for Planning Daily Drayage Operations. Central European Journal of Operations Research, 14, 141-156.

Imai, A., Nishimura, E. & Current, J. (2007). A Lagrangian relaxation-based heuristic for the vehicle routing

with full container load. European Journal of Operational Research, 176, 87–105.

Jula, H., Dessouky, M., Ioannou, P. & Chassiakos, A. (2005). Container movement by trucks in metropolitan

networks: modeling and optimization. Transportation Research Part E: Logistics and Transportation

Review, 41, 235–259.