A Decision Support System for Solving the Windy Rural Postman Problem

The problem of vehicle routing with time windows is a well-known routing problem that involves finding the shortest routes for a group of identical vehicles stationed at a central location, with the objective of delivering goods to a set of customers within a specific time frame. This chapter presents a real-world distribution problem faced by postal companies, where the goal is to minimize the number of vehicles required. Specifically, the problem we address is a vehicle routing problem with double time windows (VRPDTWs), where the first window represents travel time and the second window represents the time for postal delivery. This problem can be modeled as a variant of the windy postman problem, which is a type of VRPTW. Due to its complexity, this optimization problem is classified as NP-hard, making it difficult to solve in a reasonable amount of time. As a result, approximate methods must be used to find near-optimal solutions for VRPDTW. To tackle this problem, we propose a variable neighborhood-based approach, which we apply to real-life instances of a postal company in northwest Tunisia to demonstrate the efficiency of our algorithm.