• The weight/volume capacities of the vehicles (assume that all the vehicles are
homogeneous in this study)
3 Objective
The main objective of the proposed problem is to find out the best routing strategy
such that the total traveling distance of all the vehicles are minimized (while
reducing the total number of vehicles used for the delivery).
Constraints
1. The weight/volume capacity for all the vehicles cannot be exceeded.
2. All the modularized boxes assigned to one vehicle should be able to be
completely packed into the assigned vehicle.
3. The rule of “Last-In, First-Out” should be respected.
4. All the customers can only be visited once. That is, all the ordered modularized
boxes should be arrived at the location of the customers in a batch mode.
In the following section, we explain the algorithms used to solve the above
problem.
3.1 Resolution Approach
Both the VRP and the 3D bin packing problems are NP-hard (Pinedo, 2012). In our
case, their combination is also NP-hard since both of its subproblems are NP-hard.
Consequently, heuristic methods are required to solve the problem. In Gendreau
et al. (2006) and Massen et al. (2012), the authors used metaheuristic methods such
as Tabu search and ant colony optimization to reach near optimal solutions. Such
metaheuristics use randomness to explore better solutions. However, one of the
accompanying counter effects of such approaches is that different runs of the same
algorithm may result in different final solutions. Since, as mentioned before, the
main purpose of this last mile problem is to analyze the potential of the horizontal
collaboration, to prevent the generation of inconsistent results affected by randomness, the solving algorithms for the proposed last mile problem are deterministic
rule-based heuristics.
The master problem of the proposed last mile problem is dedicated to vehicle
routing, and three-dimensional bin packing problem plays the role of a side constraint. Our proposed algorithm introduces an insertion heuristic to solve the VRP as
master problem. As commented by Campbell and Savelsbergh (2004), insertion
heuristics have proven to be popular methods for solving a variety of vehicle routing
problems due to their computational efficiency and the ability to be easily extended
3 The Impact of Collaborative Scheduling and Routing for Interconnected. . .
43
homogeneous in this study)
3 Objective
The main objective of the proposed problem is to find out the best routing strategy
such that the total traveling distance of all the vehicles are minimized (while
reducing the total number of vehicles used for the delivery).
Constraints
1. The weight/volume capacity for all the vehicles cannot be exceeded.
2. All the modularized boxes assigned to one vehicle should be able to be
completely packed into the assigned vehicle.
3. The rule of “Last-In, First-Out” should be respected.
4. All the customers can only be visited once. That is, all the ordered modularized
boxes should be arrived at the location of the customers in a batch mode.
In the following section, we explain the algorithms used to solve the above
problem.
3.1 Resolution Approach
Both the VRP and the 3D bin packing problems are NP-hard (Pinedo, 2012). In our
case, their combination is also NP-hard since both of its subproblems are NP-hard.
Consequently, heuristic methods are required to solve the problem. In Gendreau
et al. (2006) and Massen et al. (2012), the authors used metaheuristic methods such
as Tabu search and ant colony optimization to reach near optimal solutions. Such
metaheuristics use randomness to explore better solutions. However, one of the
accompanying counter effects of such approaches is that different runs of the same
algorithm may result in different final solutions. Since, as mentioned before, the
main purpose of this last mile problem is to analyze the potential of the horizontal
collaboration, to prevent the generation of inconsistent results affected by randomness, the solving algorithms for the proposed last mile problem are deterministic
rule-based heuristics.
The master problem of the proposed last mile problem is dedicated to vehicle
routing, and three-dimensional bin packing problem plays the role of a side constraint. Our proposed algorithm introduces an insertion heuristic to solve the VRP as
master problem. As commented by Campbell and Savelsbergh (2004), insertion
heuristics have proven to be popular methods for solving a variety of vehicle routing
problems due to their computational efficiency and the ability to be easily extended
3 The Impact of Collaborative Scheduling and Routing for Interconnected. . .
43