Solution algorithms for a vehicle routing problem with route-cost equity constraints
摘要
Workload equity is an emerging topic in the routing literature. Typically, efficient solutions usually lack equity, thus, the challenge is to propose models and algorithms capable of finding solutions with an equitable workload distribution among drivers, while minimizing the impact on routing cost. In the current literature, most papers naturally manage equity within a bi-objective model. In this work, we rather use the classic min-cost objective as the single objective and manage equity on the drivers route costs with equity constraints. We use a test-bed pickup and delivery routing problem motivated by the non-emergency transportation of patients. We show that the straightforward set partitioning formulation can not be solved efficiently by a standard branch-and-price approach and propose three original solution methods: two branch-and-price algorithms and a heuristic. The proposed branch-and-price algorithms are based on new models to manage equity constraints. In the first model, the variables (columns) are indexed by a route and a driver. In the second model, equity constraints are expressed on the pickup and delivery requests instead of the drivers. The heuristic is based on a dichotomic search. Algorithms are evaluated on real-world-based instances with up to 50 transportation requests. Computational experiments highlight the pros and cons of each algorithm and show that equitable solutions can be found with a low impact on the routing cost.