A differential evolution algorithm for pickups and deliveries problem with fuzzy time windows

Abstract

In this paper, a pickups and deliveries problem with fuzzy time windows (PDPFTW) is presented and solved. The customer service level associated with time window is characterized by fuzzy membership functions based on fuzzy set theory. A novel multi-objective fuzzy programming model of PDPFTW is proposed. The proposed model aims at minimizing the vehicle numbers and the overall travel costs and maximizing the total customer service level. A novel differential evolution algorithm (DE) for PDPFTW is also proposed. In DE, we first adopted the novel decimal coding to construct an initial population, and then used some improved differential evolution operators unlike existing algorithm, in mutation operation, we used an integer order criterion based on natural number coding method and introduced a penalty technical to publish the infeasible solution. In addition, in the crossover operation, we designed a self-adapting crossover probability that varied with iteration. Our experimental results demonstrate the efficiency of the proposed DE, which saved some running time compare with GA in 100,200,400 and 1000 cases. At the same time, DE can get better solutions compare with GA in total distance of vehicles, total services level of customers and vehicle numbers. Moreover, we found that total service level would increase with wider time window.