Vehicle routing for on-site services with time window flexibility and time-dependent speeds to minimise emission cost

We study the problem of scheduling engineers who drive to customer sites to perform service tasks. Vehicle speeds and associated CO2 emissions are time-dependent. Customers specify a service time window or choose to participate in a green delivery programme by offering multiple available time windows. This new vehicle routing problem with multiple time windows and time-dependent speeds is formulated as a mixed-integer linear programming (MILP) model to minimise emission costs. The model is then extended to handle scenarios in which customers can offer optional time windows on different days. To solve large instances, we develop a self-adaptive simulated annealing algorithm. For small instances solvable by optimisation software, experimental results show that the algorithm produces near-optimal solutions efficiently. Experiments on instances of different sizes show consistent improvement of the proposed algorithm over the standard simulated annealing. The algorithm is further applied in additional experiments simulating more practical operations. Results demonstrate that incorporating time window flexibility can reduce emission costs and increase the number of customers served under overbooking conditions. Tests under various settings indicate that greater participation in the green delivery programme, or more available time windows per customer, leads to further reductions in emission costs and improved service capacity.