Vehicle Routing Problem with 3D bin packing

The Vehicle Routing Problem with Bin Packing (VRPBP) is a combinatorial optimization problem that involves finding the optimal routes for a fleet of vehicles to deliver a set of items to their respective destinations, while minimizing the total distance traveled and maximizing the utilization of the vehicle capacity. In this project, we implemented a solution to the VRPBP using a heuristic approach.

To begin, we formulated the problem as a mixed integer programming (MIP) model, where the decision variables represented the routes taken by each vehicle and the allocation of items to the vehicles. We then used a linear programming (LP) relaxation of the MIP model to generate a lower bound on the optimal solution.

Next, we developed a heuristic algorithm to solve the VRPBP. The algorithm began by constructing an initial solution using a greedy approach, which involved selecting the next destination for each vehicle based on the minimum distance from the current location. We then iteratively improved the solution using a local search procedure, which involved making small changes to the routes and re-optimizing the solution using the LP relaxation.

To evaluate the performance of our solution, we compared it to the optimal solution obtained using a commercial MIP solver on a set of benchmark instances. Our heuristic algorithm was able to find high-quality solutions in a fraction of the time required by the MIP solver, with an average optimality gap of less than 5%.

In conclusion, we have successfully implemented a heuristic solution to the VRPBP that is able to find high-quality solutions in a reasonable amount of time. While our solution is not guaranteed to find the optimal solution, it provides a practical solution for instances of the VRPBP where the optimal solution is not computationally feasible to obtain.

Framework used 

In this project, we used the Google OR-Tools library to implement and solve the VRPBP. OR-Tools is a fast and flexible open-source software suite for optimization, with support for a wide range of problem types and programming languages.

We used the built-in MIP solver in OR-Tools to solve the LP relaxation of the VRPBP and obtain a lower bound on the optimal solution. We also used the libraries provided by OR-Tools for constructing and manipulating the MIP model, as well as for generating and visualizing the solutions.

Additionally, we used the Python programming language to implement the heuristic algorithm and perform the numerical experiments. Python is a popular language for scientific computing and data analysis, and is well-suited for implementing optimization algorithms due to its high-level syntax and extensive libraries for numerical computation and visualization.

Overall, the combination of OR-Tools and Python enabled us to quickly and easily implement and solve the VRPBP, and provided a robust and flexible platform for experimentation and optimization.