A multi-thread simulated annealing for multi-objective vehicle routing problem with time windows and demand priority

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known optimization problem aimed at minimizing the total traveling distance while satisfying specified time windows. However, time windows do not always reflect customer satisfaction, as they are sometimes set based on customers' operating conditions rather than customer preferences. In this study, we propose the Vehicle Routing Problem with Time Windows and Demand Priority (VRPTWDP), a variation of VRPTW that integrates customer satisfaction into route planning. VRPTWDP is a multi-objective problem that aims to strike a balance between minimizing the total traveling distance and minimizing the total customer waiting times based on priority level. We propose a Mixed Integer Linear Programming (MILP) model for the problem and validate the model through computational experiments on small problem instances. Additionally, we introduce Multi-Thread Simulated Annealing (MTSA) that can provide high-quality Pareto frontier approximation (PFA) for large-scale VRPTWDP within a reasonable computational time compared to its original counterpart, Multi-Objective Simulated Annealing (MOSA). Results from computational experiments indicate that the proposed MTSA outperformed MOSA in terms of PFA quality, given the same computational resources. Finally, the customer priority level incorporated into the proposed model is shown to effectively allow the planner to manipulate the routes according to the customer's needs.