In this work, we deal with the problem of routing several vehicles from starting locations to destination locations via the road network. The road network has limited capacity on each section. The goal is to assign routes to vehicles in such a way as to minimize the sum of travel times. We call
the problem minimum-cost multicommodity flow problem, and we wanted to find a method powerful enough to work even on large real networks. We have implemented several different solvers. These include the greedy method, descent, Lagrange relaxation, and branch and bound method. We compared these methods with standard approaches such as the simplex method and branch and cut method. For infeasible cases, we used the bi-objective branch and bound method, and for large cases, the method that optimizes paths locally. The research involved demonstration of the methods on small synthetic examples and real-world examples and also testing on synthetic data. With this, we found that some solvers are absolutely a better choice than others.
|
