Abstract
Planning vehicles’ routes in collection and delivery operations are commonly formulated into the Vehicle Routing Problem (VRP) or one of its variants. However, the fixed plan’s assumption is no longer valid given dynamic updates; hence the Dynamic variant (DVRP) is evolved; however, limited to dynamic customer updates. Resource updates are rarely tackled, particularly vehicle breakdowns requiring adequate workload distribution measures acrossother vehicles. Traditional optimisation approaches are deemed inappropriate due to their inflexibility and time-consuming in producing optimal routes. Therefore, this thesis explores the emerging agent-based optimisation approach for dynamic problems and proposes an agent-based conceptual model to represent, simulate and optimise the problem.
The novelty of this thesis lies in designing the proper agents’ interactions to optimise the problem, two of which are proposed based on a different degree of centralisation of the agents’ interactions. First, a distributed interaction approach is proposed to construct routes sequentially, dubbed hybrid, given its slight centralisation with priority rules. Unique feasibility evaluations are proposed to address each vehicle agent’s unique attributes. The second is a centralised approach that performs extensive global and multiple objective
improvements aided by a population-based metaheuristic framework. A distinction is made between problem-dependent and the multi-objective metaheuristic framework components for which novel agent-based problem representation and evaluation are proposed. A Pareto dominance sorting is implemented without prioritising any of the objectives.
For verification and validation, tests on benchmark instances were run, resulting in a reduction of around 5% in vehicles used (hybrid) and 2.20-time units in total waiting times (centralised) at the expense of the total distance travelled. Furthermore, benchmark instances are modified to tackle the breakdown instant problem by randomising locations in addition to capacities and operating shifts and run to justify the applicability of the proposed model.
Finally, a case study is adopted to validate the proposed approaches for a multiple breakdown case. A significant reduction in distance of around 68% and 100% elimination of constraint violations have resulted in the static scenario. Furthermore, the disrupted workload can be efficiently re-optimised with minimum deviation from the original static planned routes experimented under three different dynamic breakdown scenarios.
| Date of Award | 2023 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Ammar Al Bazi (Supervisor) & Vasile Palade (Supervisor) |