Vehicle routing problem with fuzzy time windows

In this paper, a vehicle routing problem with fuzzy time windows (VRPFTW) is proposed and solved. In the transportation business, time windows are not always strictly obeyed and the deviation of service time from the customer-specific time window determines the customerʹs satisfaction level, which can also be regarded as the supplierʹs service level. This paper applies fuzzy membership functions to characterize the service level issues associated with time window violation in a vehicle routing problem and proposes VRPFTW. VRPFTW is formulated as a multi-objective model with two goals: (1) to minimize the travel distance and (2) to maximize the service level of the supplier to customers. To solve this multi-objective model, a two-stage algorithm is developed to obtain a Pareto solution for VRPFTW. Using the two-stage algorithm, VRPFTW is decomposed into two subproblems, namely a traditional vehicle routing problem with time windows (VRPTW-α) and a service improvement problem, and each of the objectives is sequentially solved. The service improvement problem is solved under two different scenarios. When the fuzzy membership function is linear, it is shown that the service improvement problem can be solved by the cutting plane algorithm within finite iterations, and when the fuzzy membership function is concave, the service improvement problem can be solved by a subgradient-based algorithm. Moreover, an alternative formulation of VRPFTW is also proposed and analyzed. Experiments are conducted to compare different models of vehicle routing problems with time windows in situations where violation of time windows is allowed, and the results show that the VRPFTW model can achieve considerable cost-savings, while at the same time maintaining an acceptable service level.