A cluster insertion-based heuristic with load-dependent service times and transportation costs for the vehicle routing problem with backhauls and time windows

• Main Author: Gutierrez, Michael R.
• Format: text
• Language: English
• Published: Animo Repository 2013
• Subjects: Vehicle routing problem; Industrial Engineering
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/6911
• Institution: De La Salle University

The Vehicle Routing Problem with Backhauls and Time Windows is an extension of the famous optimization problem, Vehicle Routing Problem. It deals with the construction of an optimal route for a vehicle that minimizes a certain cost function whilst ensuring that delivery demand is met for all linehaul customers and pickup demand is met for all backhaul customers within the network. Currently, there are two existing approaches to solving the problem—the classical approach and the mixed approach— but neither are able to optimize the problem fully because of the complications brought about by backhauling. The study has broken them down into two main complications: load reshuffling and increased gas consumption. Backhauling entails blocking the passage of goods within the vehicle; hence, deliveries are harder to make and take longer when backhaul load is present on the truck. Additionally, backhauling also makes the vehicle significantly heavier due to cargo load; hence, it consumes more fuel along the route. To address this, the study proposes a third and optimal approach for solving the VRPBTW—one that incorporates load-dependent service times and load-dependent transportation costs. To address this problem, the study formulates a mixed-integer, non-linear programming model to represent the proposed approach that incorporates load-dependent service times and transportation costs. The approach minimizes transportation costs, penalty costs and time-based costs Due to the factorial complexity of the VRPBTW, however, a heuristic methodology is deemed more appropriate and usable for solving large-sized problems. Because of this, the study also creates a cluster insertion-based heuristic based on the logic of the formulated model. The created heuristic makes use of the concept of insertion, such that postulates the creation of an initial route using only the linehaul customers, then proceeds to insert the backhauls in between the linehaul customers of the initial route. Furthermore, cluster insertions—a more advanced feature of insertion heuristics—allows for the insertion of multiple backhaul nodes in between two linehauls; hence, improving the solution quality of the heuristic procedure. Both the MINLP and the heuristic is applied on a formulated network problem with 5 linehaul customers, 3 backhaul customers and 1 depot. Both the model and the heuristic come up with the same solution, indicating that the heuristic is capable of the best possible solution to the problem given its size. By solving the same network problem through a mixed approach and a classical approach, it is seen that the proposed approach is able to minimize the total costs of the system compared to the two other approaches when considering load-dependent transportation costs and service times. The proposed approach strikes a significant improvement on the solutions of the two existing approaches, and furthermore, achieves Pareto optimality between cost and time component tradeoffs. . The sensitivity analysis also reveals that the heuristic demonstrates weakness under certain scenarios. Particularly, it begins to lose its ability to come up with the best possible solution when the sensitivity between load and transportation costs is low, but the one between load and service time is high. Complexity analysis is performed on the heuristic procedure, and it is revealed that the heuristic begins to simplify computational complexity of solving the VRPBTW for problems with a size of 7 nodes or bigger; any problems smaller than this is easier to compute via exact means. Lastly, the study comes up with an executable computer program, the Load-Dependent VRPBTW Solution program, which users can use to apply the heuristic on their own VRPBTW problem networks. The program makes it possible for users to solve large scale problems quickly while incorporating loaddependencies, a feature which is not available in other VRP software.