vehicles. The Tabu search starts with a randomly generated solution. Then, for each
route found by the Tabu search, the tree search algorithm tries to generate a packing
plan where all boxes are placed correctly. Each node of the tree has three elements: a
partial solution of placements, a set of free boxes that must be placed, and a list of
potential placements. The algorithm tries to add placements for each free box until
all are placed, or a time limit has been reached, or one box has no possible
placement.
In Massen et al. (2012), for a similar problem, it uses an ant colony algorithm
combined with a column generation algorithm which is used to solve large linear
programming programs. Column generation generates only the variables which can
potentially improve the objective function.
Only very small instances for the bin packing problem have been solved to
optimality. Some exact methods were proposed by Martello et al. (2000). For bigger
instances, only heuristic methods have been developed. In Hifi et al. (2010), the
authors consider the assignment of items to identical bins. The packings have to be
feasible, and their aim is to minimize the number of bins needed. n items characterized by a width w i , a height h i , and a depth d i (i ¼ 1,2,. . .. . .,n) are put in identical
bins with width W, height H, and depth D. By using integer linear programming,
they are able to find solutions for the bin packing. The constraints that must be
satisfied are expressed as inequalities.
In Levine and Ducatelle (2004), an ant colony optimization is presented, in order
to solve bin packing and cutting stocks problems. It is inspired by the capability of
ants to find the shortest path between their nest and a food location by using
pheromone trails.
The authors in Fanslau and Bortfeldt (2010) present a tree search algorithm to
solve the 3D container loading problem for weakly or strongly heterogeneous items
(i.e., same or different dimensions). They fill a container by adding blocks which are
arrangements of one or more oriented boxes (items). The blocks are placed in
residual spaces. In order to find the best block for a residual space, a tree search
is used.
Our research is closest to the works of Gendreau et al. (2006) and Massen et al.
(2012); however, our research in this chapter focuses on the impact of horizontal
collaboration for the last mile delivery in the context of Physical Internet. This leads
to better usage of capacities and reducing the operational cost as well as the number
of vehicles required to deliver products.
1.3 The Vehicle Dispatching Problem
Physical Internet hubs are the places where modularized containers are sorted,
assembled, and packed into vehicles. According to the concept of the Physical
Internet, the short-range transportation is encouraged, which means that if possible,
all the transportation activities are ideal to be limited between a Physical Internet hub
and one of its neighboring hubs. The rational of such a recommendation is to
38
Sh. Sharif Azadeh et al.
route found by the Tabu search, the tree search algorithm tries to generate a packing
plan where all boxes are placed correctly. Each node of the tree has three elements: a
partial solution of placements, a set of free boxes that must be placed, and a list of
potential placements. The algorithm tries to add placements for each free box until
all are placed, or a time limit has been reached, or one box has no possible
placement.
In Massen et al. (2012), for a similar problem, it uses an ant colony algorithm
combined with a column generation algorithm which is used to solve large linear
programming programs. Column generation generates only the variables which can
potentially improve the objective function.
Only very small instances for the bin packing problem have been solved to
optimality. Some exact methods were proposed by Martello et al. (2000). For bigger
instances, only heuristic methods have been developed. In Hifi et al. (2010), the
authors consider the assignment of items to identical bins. The packings have to be
feasible, and their aim is to minimize the number of bins needed. n items characterized by a width w i , a height h i , and a depth d i (i ¼ 1,2,. . .. . .,n) are put in identical
bins with width W, height H, and depth D. By using integer linear programming,
they are able to find solutions for the bin packing. The constraints that must be
satisfied are expressed as inequalities.
In Levine and Ducatelle (2004), an ant colony optimization is presented, in order
to solve bin packing and cutting stocks problems. It is inspired by the capability of
ants to find the shortest path between their nest and a food location by using
pheromone trails.
The authors in Fanslau and Bortfeldt (2010) present a tree search algorithm to
solve the 3D container loading problem for weakly or strongly heterogeneous items
(i.e., same or different dimensions). They fill a container by adding blocks which are
arrangements of one or more oriented boxes (items). The blocks are placed in
residual spaces. In order to find the best block for a residual space, a tree search
is used.
Our research is closest to the works of Gendreau et al. (2006) and Massen et al.
(2012); however, our research in this chapter focuses on the impact of horizontal
collaboration for the last mile delivery in the context of Physical Internet. This leads
to better usage of capacities and reducing the operational cost as well as the number
of vehicles required to deliver products.
1.3 The Vehicle Dispatching Problem
Physical Internet hubs are the places where modularized containers are sorted,
assembled, and packed into vehicles. According to the concept of the Physical
Internet, the short-range transportation is encouraged, which means that if possible,
all the transportation activities are ideal to be limited between a Physical Internet hub
and one of its neighboring hubs. The rational of such a recommendation is to
38
Sh. Sharif Azadeh et al.