The fuzzy multi-depot vehicle routing problem with simultaneous pickup and delivery: Formulation and a heuristic algorithm

Abstract

In this paper, the fuzzy multi-depot vehicle routing problem with simultaneous pickup and delivery (FMDVRP-SPD) is investigated. The FMDVRP-SPD is the problem of allocating customers to several depots, so that the optimal set of routes is determined simultaneously to serve the pickup and the delivery demands of each customer within scattered depots. In the problem, both pickup and delivery demands of customers are fuzzy variables. The objective of FMDVRP-SPD is to minimize the total cost of a distribution system including vehicle traveling cost and vehicle fixed cost. To model the problem, a fuzzy chance-constrained programming model is proposed based on the fuzzy credibility theory. A heuristic algorithm combining K-means clustering algorithm and ant colony optimization is developed for solving the problem. To achieve an appropriate threshold value of parameters of the model, named “vehicle indexes”, and to analyze their influences on the final solution, numerical experiments are carried out.

Keywords

• vehicle routing problem
• simultaneous pickup and delivery
• fuzzy demand
• K-means clustering algorithm.