Vehicle routing optimization with soft time windows in a fuzzy random environment

Abstract

This paper is concerned with a vehicle routing problem with soft time windows (VRPSTW) in a fuzzy random environment. Two objectives are considered: (1) minimize the total travel cost and (2) maximize the average satisfaction level of all customers. After setting up the model for the VRPSTW in a fuzzy random environment, the fuzzy random expected value concept is used to deal with the constraints and its equivalent crisp model is derived. The global–local–neighbor particle swarm optimization with exchangeable particles (GLNPSO-ep) is employed to solve the equivalent crisp model. A case study is also presented to illustrate the effectiveness of the proposed approach.

Introduction

Vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. It is always described as a problem of designing optimal delivery or collection routes from one or several depots to a number of geographically scattered cities or customers, subject to side constraints, see e.g. Laporte (1992). Since VRP was first proposed by Dantzig and Ramser (1959), it has been studied extensively, see e.g. Qarke and Wright, 1964, Bertsimas, 1992, Gutiérrez-Jarpa et al., 2009, Solomon, 1987, Liu and Lai, 2009.

The vehicle routing problem with time windows (VRPTW) considers the time windows of each customer and makes sure that the services must start in their time windows. It has attracted more and more attention and been widely studied recently. For example, Lee et al. (2003) presented a vehicle capacity planning system (VCPS) to solve the VRPTW under the condition of outsourcing some operations to local transportation companies due to capacity limits. Aminu and Eglese (2006) solved Chinese postman problem with time windows by transforming it to an equivalent VRPTW, and discussed the relationship between the time windows and the results. Alvarenga et al. (2007) proposed a robust heuristic approach for the VRPTW using travel distance as the main objective through an efficient genetic algorithm and a set partitioning formulation. Figliozzi (2009) studied approximations to the average length of VRPTW, route duration, and capacity constraints. Cheng and Wang (2009) solved a VRPTW by a decomposition technique and a genetic algorithm.

There are two types of VRPTW: vehicle routing problems with crisp or hard time windows (VRPHTW) and vehicle routing problems with soft time windows (VRPSTW). The hard time windows are often violated for some reasons as given in Tang et al. (2009): (1) Relaxing the constraints of hard time windows can result in better solutions. (2) Sometimes no feasible solution could be found if all time window constraints need to be satisfied. (3) A customer may demand a “narrower” time window than needed, while in fact, a little bit deviation from the specified time window is acceptable to the customer. Therefore the soft time windows are more related to reality. Sexton and Choi (1986) firstly considered the soft time windows. Ferland and Fortin (1989) introduced a heuristic approach for the vehicle scheduling problem with sliding time windows. Min (1991) developed a model that considers both time windows and analyzes the tradeoff between time and cost, and applied it to the case of a public library distribution system in the Columbus, Ohio metropolitan area. Balakrishnan (1993) proposed simple heuristics to solve the VRPSTW. Guo and Mak (2004) studied the VRPSTW with uncertain customer demands, and proposed a genetic based algorithm to solve the problem. Hashimoto et al. (2006) used local search to determine the routes of vehicles and the optimal start times of services at visited customers in the VRP with flexible time windows and travel times.

However, there exists some uncertain information in the VRPSTW, which has been hardly considered in the literature. For example, the time windows are usually acquired by a survey or an interview, and described as some ambiguous statements, such as “about at 2 clock” or “it is better no later than 16:00”. In the mean time, some stochastic factors are involved in the VRPSTW too: (1) one node usually has more than one person in charge, the choice of respondents is stochastic; (2) due to reasons such as season, whether and type of respondents (optimistic or pessimistic), the customers usually give different time windows. That is to say, the statements of time windows often contain some stochastic influencing factors. Therefore, the VRPSTW should be considered with such stochastic and ambiguous information. Since first proposed by Zadeh (1965), fuzzy theory has been a useful tool to deal with ambiguous information, while stochastic theory is proper to handle the stochastic influencing factors.

In this paper, the VRPSTW in a fuzzy random environment is considered and the fuzzy random theory is used to deal with such uncertain information in the VRPSTW. Fuzzy random variables represent a well-formalized concept underlying many recent probabilistic and statistical studies involving data obtained from a random experiment when these data are assumed to be fuzzy set valued (Gil et al., 2006). It has been applied in many fields, see e.g. Li and Xu, 2006, Liu and Xu, 2008, Näther, 2006, Sakalli, 2010. However there are few researchers who have considered the fuzzy random factors in VRP. Malekly et al. (2009) considered a capacitated VRP whose demands are assumed to be fuzzy random variables. For the VRPSTW, to our best knowledge, fuzzy random theory has never been applied to describe the time windows which contain such uncertain information. The “endurable earliness time” and “endurable lateness time” proposed by Tang et al. (2009) are adopted to describe the time windows, which are regarded as fuzzy random variables.

The rest of this paper is organized as follows. In Section 2, some introduction about the soft time windows in fuzzy random environment and the satisfaction levels with the soft time windows are given, then a multi-objective linear programming model is set up and its equivalent crisp model is derived. In Section 3, the global–local–neighbor particle swarm optimization with exchangeable particles (GLNPSO-ep) is proposed to solve the model. The application to the Ertan large-scale water conservancy and hydropower construction project is presented in Section 4. Concluding remarks are given in Section 5.