Abstract
This case study tackles a real-world problem of a transportation company that is modeled as a scheduling optimization problem. The main goal of the considered problem is to schedule the maximum number of jobs that must be performed by vehicles over a specific planning horizon in order to minimize the total operational costs. Here, each customer request corresponds to a job composed of multiple operations, such as loading, unloading, and mandatory jobs, each associated with a specific location and time window. Once a job is allocated to a vehicle, all its operations must be executed by that same vehicle within their designated time constraints. Due to the imposed limitations, not every job can feasibly be scheduled. To address this challenge, two distinct methodologies are proposed. The first, a Holistic approach, solves the entire problem formulation using a black-box optimizer, serving as a comprehensive benchmark. The second, a Divide-and-Conquer approach, combines a heuristic greedy algorithm with a binary linear programming, decomposing the problem into sequential subproblems. Both approaches are implemented using the solver Hexaly. A comparative analysis is conducted under different scenarios and problem settings to highlight the advantages and drawbacks of each approach. The results show that the Divide-and-Conquer approach significantly improves computational efficiency, reducing time by up to 99% and vehicle usage by around 15–20% compared to the Holistic method. On the other hand, the Holistic method better ensures that mandatory jobs are completed, although at the cost of more resources.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.