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 202

Email: mvidovic@sf.bg.ac.rs

Miloš Nikolić

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

The containers drayage problem 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

20ft, and 40ft 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 the time windows that ﬁnds an

optimal set of or routes visiting deliveries and pickups customers. The specificity of the container drayage

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

of Serbia, through the projects TR 36002 and TR 36006, for the period 2011-2014.

Milorad Vidović, Miloš Nikolić and Dražen Popović

24

1 INTRODUCTION

The routing problem studied here is a typical for the intermodal transportation systems where containers

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

satisfied, it is also possible to move the empty containers directly to a shipper instead of hauling them back to

the terminal’s depot and having them transferred latter. From there, when considering container transportation

within a local region oriented to an intermodal terminal that includes empty containers’ depot, few possible

types of container moves, also known as drayage operations (Macharis & Bontekoning, 2004), can be

recognized (Fig. 1b).

Drayage operations are driven by the need to fulfill customer demands while satisfying various constraints

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)

Most intermodal containers are sized according to International Standards Organization (ISO). Based on

ISO, containers are classified in several groups (10ft, 20ft, 30ft, 40ft, 45ft and since recently 48ft and 53ft),

where 20ft and 40ft containers are the most frequently used all over the world. An important issue in containers

pickup and delivery is coordination of the dimensions of road transport vehicles with the dimensions of

intermodal containers. In Europe, except Finland and Sweden, and Asia, road vehicles are restricted to transport

only 20ft and 40ft containers, only few countries allow 45ft containers, while larger containers are in use only in

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.

Drayage operations and especially container truck transportation account for a significant portion of the

total transportation cost. Therefore, it is very important to improve the efficiency of container transportation

Int. Journal of Business Science and Applied Management / Business-and-Management.org

25

through the optimization of such transportation processes, which leads to necessity of solving the truck

scheduling problem in container drayage operation (Zhang et al. 2010).

Optimization of container drayage operation has received increased attention over the past decade due to its

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 ﬂeet of trucks

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

system. Zhang et al. (2010), considered a truck scheduling problem for container transportation in a local area

with multiple depots and multiple terminals. They proposed an approach based on an integer programming

heuristic determines pickup and delivery sequences for daily drayage operations with minimum transportation

cost. Savelsbergh and Sol (1995) show that container transportation problems belong to pickup and delivery

problems, and because of the nature of the problem, drayage operations also corresponds to multi-stop Vehicle

Routing Problems with Backhauls (VRPB). A more detailed insight in VRPB, as well as in Vehicle Routing

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

consignee are to a shipper’s, as a relatively rare tasks, are not considered.

In the container drayage operations realized by combined chassis vehicles, VRPBTW refers to the problem

where up to four nodes can be visited in a single route starting and ending in container terminal or depot which

is assumed here to be part of the terminal.

Our research extends the problem analyzed by Zhang et al. (2010) to the multi-commodity case, but for the

case when only one intermodal terminal operates in the region. Also, our research extends the problem analyzed

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,

and loaded (export i.e. outbound containers), as well as empty containers should be picked up at a customers’

sites and hauled back to the terminal. Therefore, when truck tow combined chassis, matching possibilities

include all feasible combinations of 20ft, and 40ft containers that should be transported from/to terminal and

customers (Figure2). Obviously, as it can be seen from the Figure 2, there are several possible routes realization

concepts and it is worthwhile to choose those resulting with minimal length.

Milorad Vidović, Miloš Nikolić and Dražen Popović

26

Figure 2: Some of routing possibilities when drayage is realized by combined chassis

2.1 Multiple assignment formulation of the container drayage problem

Let

N,EG

be a graph, where N is the set of nodes

Ni

with containers move requests, and

NjijijiE ,,|),(

is the edge set. It is assumed that any node may simultaneously have both, containers

demand and supply move requests. Number of requests in all nodes

40402020

,,,

i

nnnn

iii

which correspond to

20ft containers demand (20-) and supply (20+), and 40ft containers demand (40-) and supply (40+) are known in

advance. All containers are available at the beginning of the planning horizon (usually one day), and all vehicles

start from the terminal. The assumption that node may simultaneously have demand and supply move requests,

gives opportunity of transforming graph into the another, in which each node

Ni

is replaced with

40402020

i

nnnnn

iiii

task nodes. In this way all task nodes of the transformed graph, whose indexes

are renumerated, have single move requests, either pickup or delivery (20ft, or 40ft containers).

The set of all task nodes with renumerated indexes, can be now partitioned into four subsets,

40402020

,, NandNNN

. Sets N

20-

, and N

40-

contain only delivery, while sets N

20+

, and N

40+

include only

pickup nodes with 20ft, and 40ft containers respectively. In this network, when using a combined chassis, there

are fifteen possible matchings of task nodes into merged routes, and four direct pickup or delivery routes:

Four nodes matchings:

Terminal → -20 → -20 → +20 → +20 →Terminal

Terminal → -20 → +20 → -20 → +20 →Terminal

Three nodes matchings:

Terminal → -20 → -20 → +20 →Terminal

Terminal → -20 → +20 → +20 →Terminal

Terminal → -20 → +20 → -20 →Terminal

Terminal → +20 → -20 → +20 →Terminal

Terminal → -20 → -20 → +40 →Terminal

Terminal → -40 → +20 → +20 →Terminal

Two nodes matchings:

Terminal → -40 → +40 →Terminal

Terminal → -20 → +40 →Terminal

Terminal → -40 → +20 →Terminal

Terminal → -20 → +20 →Terminal

Terminal → +20 → -20 →Terminal

Terminal → +20 → +20 →Terminal

Terminal → -20 → -20 →Terminal

Direct pickup or delivery routes:

Terminal → +20 →Terminal

Terminal → -20 →Terminal

Terminal → +40 →Terminal

Terminal → -40 →Terminal

Int. Journal of Business Science and Applied Management / Business-and-Management.org

27

Then, the container drayage problem with time windows, when combined chassis is used, can be

formulated as the following problem of assigning (matching) nodes in the same route which forms backhaul

loop.

4040202020 2020 20

20 2020 2040 2020 4040 40

40 20 2020 20 4020 20 20

20 20 2020 20 2020 20 20

20 20 20 2020 20 20 20

min

Nt

tt

Nz

zz

Np

pp

Nw

wwwe

Nw Ne

wepq

Np Nq

pq

wp

Nw Np

wppw

Np Nw

pwtw

Nt Nw

twpz

Np Nz

pztz

Nt Nz

tz

twe

Nt Nw ewNe

twepqz

Np qpNq Nz

pqzpwq

Np Nw qpNq

pwq

wpe

Nw Np ewNe

wpepwe

Np Nw ewNe

pwepqw

Np qpNq Nw

pqw

pwqe

Np Nw qpNq ewNe

pwqepqwe

Np qpNq Nw ewNe

pqwe

cycycycycycy

cycycycycy

cycycy

cycycy

cycy

(1)

subject to

20

1

202020

4020 4020 2020 2020 20

20 2020 20 2020 20 20

Npyyyy

yyyyy

yyy

p

qpNq

pq

Nw

wp

Nw

pw

Nz

pz

qpNq Nz

pqz

Nw qpNq

pwq

Nw ewNe

wpe

Nw ewNe

pwe

qpNq Nw

pqw

Nw qpNq ewNe

pwqe

qpNq Nw ewNe

pqwe

(2)

20

1

2020

204040 2020 2020 20

20 2020 2020 20 2020 20 20

Nwyyy

yyyyy

yyyy

w

ewNe

we

Np

wp

Np

pw

Nt

tw

Nt ewNe

twe

Np qpNq

pwq

Np ewNe

wpe

Np ewNe

pwe

Np qpNq

pqw

Np qpNq ewNe

pwqe

Np qpNq ewNe

pqwe

(3)

40

1

204020 20

Nzyyyy

z

Np

pz

Nt

tz

Np qpNq

pqz

(4)

Error! Objects cannot be created from editing field codes. (5)

)1(

,,,)1(

)1(

2020

pqwewewewwe

pqweqwqwqqw

pqwepqpqppq

yMtsww

NNewqpyMtsww

yMtsww

(6)

40402020

,,)1(

)1(

NNNNwqpyMtsww

yMtsww

pqwqwqwqqw

pqwpqpqppq

(7)

40402020

,)1( NNNNqpyMtsww

pqpqpqppq

(8)

40402020

NNNNpbwa

ppp

(9)

otherwise

routesametheinmergedarelandkjinodesif

y

ijkl

,0

,,,1

(10)

otherwise

routesametheinmergedarekandjinodesif

y

ijk

,0

,,1

(11)

otherwise

routesametheinmergedarejandinodesif

y

ij

,0

,1

(12)

Milorad Vidović, Miloš Nikolić and Dražen Popović

28

otherwise

routedirecttheinservedisinodeif

y

i

,0

,1

(13)

Where

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

N

20-

, w,e

N

20+

)

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

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

N

20-

set of 20ft containers delivery nodes

N

20+

set of 20ft containers pickup nodes

N

40-

set of 40ft containers delivery nodes

N

40+

set of 40ft containers pickup nodes

w

p

,w

q

,w

w

,w

e

continuous variable indicating the time at which vehicle starts servicing node p,q,w,e

respectively

a

p

,b

p

the left and the right bound of the time window [a

p

.b

p

] at the node p indicating the time

interval when the node is available for the servicing

s

p

,s

q

,s

w

service times at nodes p,q,w respectively

t

pq

,t

qw

,t

we

travel times between nodes p-q,q-w,w-e, respectively

M

pq

,M

qw

,M

we

constants used to linearize time windows constraints, M

pq

=max[0, b

p

+s

p

+t

pq

-a

q

]

c

pqwe

, c

pqw

, c

pq

, c

p

costs of visiting nodes in a single route, including costs from/to terminal (0) (number of

indexes denote number of nodes merged in the same route), c

pqwe

= c

0p

+c

pq

+c

qw

+c

we

+c

e0

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

that each node in the sequence must be visited during its available time period.

2.2 General MIP formulation of the VRP with simultaneous pickups and deliveries for the container

drayage problem

The second mathematical formulation we employed here to solve the container drayage problem is based

on the general mixed integer programming model for the vehicle routing problem with simultaneous pickups

and deliveries (VRP-SPDTW), proposed by Mingyong and Erbao (2010). This model contained some classical

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

ENG ,

be a graph, where N is the set of nodes

Ni

with

containers move requests, and

NjijijiE ,,|),(

is the edge set. Node with index 0 represents the

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

requests, either pickup or delivery. It is assumed that the transport costs between task nodes which belong to the

same customer node may be neglected.

In the model we used the following notation:

n – number of task nodes to be served

– total number of vehicles

Q – vehicle capacity

c

ij

– transport costs between customer nodes i and j

k

Int. Journal of Business Science and Applied Management / Business-and-Management.org

29

x

ijk

-binary decision variable equals to 1 if and only if vehicle k travel from the task node i to the task node j

y

ij

– integer variable representing number of containers (transport equivalent units – TEU, denoting 20ft

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

z

ij

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

transported in arc i,jE

s

ik

– time of beginning of service at task node i by the vehicle k

t

i

– service time in the task node i

t

ij

– travel time between task nodes i and j

The model:

n

i

n

j

k

k

ijkij

xc

0 0 1

min

(14)

st.

njx

n

i

k

k

ijk

,11

0 1

(15)

kknjxx

n

i

jik

n

i

ijk

,1;,10

00

(16)

kkx

n

j

jk

,11

1

0

(17)

njpyy

j

n

i

ij

n

i

ji

,1

00

(18)

njdzz

j

n

i

ji

n

i

ij

,1

00

(19)

jinjnixQzy

k

k

ijkijij

;,0;,0

1

(20)

kkjinjnisxMtts

jkijkijiik

,1;;,1;,01

(21)

nikkbsa

iiki

,1;,1

(22)

kkjinjnizyx

ijijijkl

,1;;,0;,0,0,0,1,0

(23)

The objective function (14) seeks to minimize total transport costs. Constraints (15) ensure that each task

node is visited exactly once, while constraints (16) guarantee that the same vehicle arrives and departs from

each task node it serves. Constraints (17) prevent multiple depart of the vehicle from the terminal, in the same

route. Constraints (18) and (19) are flow equations for pick-up and delivery demands, respectively. Constraints

(20) prevent vehicle overloading. Constraints (21) and (22) are time windows constraints. Constraints (23)

define variables domains.

3 COMPUTATIONAL RESULTS

Testing the quality of proposed approaches to solving the container drayage problem when combined

chassis is used has been carried out on the several problem instances.

Our idea was to test the two MIP models on the Solomon VRPTW benchmark problems

(http://web.cba.neu.edu/~msolomon/problems.htm). There are six different sets of problem instances. Task

nodes are randomly generated in problem sets R1 and R2, clustered in problem sets C1 and C2, and both,

randomized and clustered in problem sets RC1 and RC2. Also, problem sets R1, C1 and RC1 have a short

scheduling horizon (few costumers per route) while problem sets R2, C2 and RC2 have a long scheduling

horizon (many costumers per route). Demand at each task node in original Solomon instances can have up to 50

units. In the problem of container drayage we observe only several containers that need to be picked from or

delivered to each task node. Therefore, we have transformed the original Solomon instances to have both pickup

and delivery task, to have fewer tasks per each node and to have four types of tasks. Total number of tasks in

Milorad Vidović, Miloš Nikolić and Dražen Popović

30

each node is obtained by dividing the original Solomon demand by 20 and rounding that number to greater

integer value. Then, we randomly allocate derived tasks to

40402020

,, NandNNN

.

Solomon instances have 100 task nodes and optimal solution for container drayage problem cannot be

obtained from instances with so many task nodes, and therefore we observe following three cases: small scale

problems with 10 and 15 task nodes and large scale problems with 50 task nodes (only first 10, 15 or 50 task

nodes are observed in each instance). In each case we observe only the first two instances from the problem set

(to provide clarity of the results presentation). The results for the small scale problem instances are presented in

Table 1 and for the large scale problem instances in Table 2. Mathematical models were implemented through

Python 2.6 API of the CPLEX 12.2. on the Intel(R) Core(TM) i3 CPU M380 2.53 Ghz with 6 GB RAM.

Table 1: Results for smaller problem instances

Number of

network

nodes

Instance

Number of

move

requests

MULTIPLE ASSIGNMENT

FORMULATION

GENERAL MIP

FORMULATION

Solution

CPU time

(sec)

Solution

CPU time

(sec)

10

C1 01

11

16964

0.01

16964

0.32

C1 02

11

22427

0.08

22427 *

1800.00

C2 01

11

34312

0.02

34312

0.63

C2 02

11

32869

0.01

32869

4.02

R1 01

11

33572

0.02

33572

0.11

R1 02

11

31214

0.01

31214

72.75

R2 01

11

29931

0.03

29931

4.91

R2 02

11

30128

0.02

30128

2.06

RC1 01

13

40883

0.03

40883

773.81

RC1 02

13

46712

0.02

46712

1519.54

RC2 01

13

50344

0.02

50344

256.76

RC2 02

13

48646

0.03

48646 *

1800.00

15

C1 01

17

51797

0.05

51797

1.53

C1 02

17

46853

0.13

46853

743.73

C2 01

17

42562

0.03

42562

17.66

C2 02

17

42856

0.05

42856

671.06

R1 01

18

40310

0.05

40310

1347.19

R1 02

18

43257

0.17

43257 *

1800.00

R2 01

18

69170

0.02

69170

60.76

R2 02

18

55820

0.02

55820

722.27

RC1 01

19

63943

0.03

63943

26.78

RC1 02

19

71521

0.05

71652 *

1800.00

RC2 01

19

74242

0.05

74242 *

1800.00

RC2 02

19

70742

0.20

73245 *

1800.00

* Solution obtained after 1800 sec of CPU time (gap between primal and dual was greater than zero)

Int. Journal of Business Science and Applied Management / Business-and-Management.org

31

Table 2: Results for larger problem instances (general MIP formulation cannot solve large scale problem

instances in reasonable CPU time)

Number of

network

nodes

Instance

Number

of move

requests

MULTIPLE ASSIGNMENT

FORMULATION

Solution

CPU time

(sec)

50

C1 01

59

141884

2.51

C1 02

59

140580

87.23

C2 01

59

184631

1.66

C2 02

59

167359

23.01

R1 01

60

204776

0.36

R1 02

60

190796

25.46

R2 01

60

174357

11.63

R2 02

60

163288

123.51

RC1 01

63

256907

1.42

RC1 02

63

264194

4.84

RC2 01

63

244955

10.68

RC2 02

63

244982

78.58

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

more detailed analysis is left for the further phases. This conclusion is drawn from the observation of Wang and

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.

However, having in mind that Imai et al. (2007) have shown that even the simpler version of the container

drayage problem - routing problem with full container load (VRPFC) is NP-hard, appropriate heuristics

approach development should be important direction of future research. Namely, the problem studied by Imai et

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

of its parts is NP-hard. Developing adequate software support, more detailed analysis of proposed approach

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.

REFERENCES

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,

252-262.

Coslovich, L., Pesenti, R. & Ukovich, W. (2006). Minimizing ﬂeet operating costs for a container transportation

company. European Journal of Operational Research, 171, 776–786.

Crainic, T.G. & Kim, K.H. (2007). Intermodal transportation. In: Barnhart C, Laporte G (Eds) Handbook in OR

& MS, 14 Elsevier B.V., 467–537.

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.

Milorad Vidović, Miloš Nikolić and Dražen Popović

32

Macharis, C. & Bontekoning, Y.M. (2004). Opportunities for OR in intermodal freight transport research: a

review. European Journal of Operational Research, 153, 400–416.

Mingyong L. & Erbao C. (2010). An improved differential evolution algorithm for vehicle routing problem with

simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence

23, 188-195.

Nagl, P. (2007). Longer combination vehicles (LCV) for Asia and Pacific region: Some economic implications.

UNESCAP Working Papers, No.2, United Nations.

Namboothiri, R. & Erera, A.L. (2008). Planning local container drayage operations given a port access

appointment system. Transportation Research Part E: Logistics and Transportation Review, 44, 185–202.

Parragh, S.,·Doerner, K. & Hartl, R. (2008a). A survey on pickup and delivery problems Part I: Transportation

between customers and depot. Journal für Betriebswirtschaft, 58, 21-51, DOI: 10.1007/s11301-008-0033-

7.

Parragh, S.,·Doerner, K. & Hartl, R. (2008b). A survey on pickup and delivery problems Part II: Transportation

between pickup and delivery locations. Journal für Betriebswirtschaft, 58, 81-117, DOI: 10.1007/s11301-

008-0036-4.

Savelsbergh, M.W.P. & Sol, M. (1995). The general pickup and delivery problem. Transportation Science, 29,

17–29.

Vidović, M., Radivojević, G. & Ratković, B. (2011). Vehicle routing in containers pickup up and delivery

processes. Procedia Social and Behavioral Sciences, 20, 335–343.

Vidović, M., Radivojević, G., Ratković, B., Bjelic, N. & Popovic, D. (2012). Containers drayage problem with

time windows. CD book of proceedings of the 15

th

International conference on transport science ICTS

2012, Portoroz, Slovenia.

Wang, X. & Regan C.A. (2002). Local truckload pickup and delivery with hard time window constraints.

Transportation Research Part B: Methodological, 36, 97-112.

Zhang, R., Yun, W.Y. & Kopfer, H. (2010). Heuristic-based truck scheduling for inland container

transportation. OR Spectrum, 32, 787–808.