مدل بهینه سازی کلونی مورچه: مشکل دوره مسیریابی وسیله نقلیه همراه با پنجره زمانی

This paper proposes an improved ant colony optimization (IACO) to solve period vehicle routing problem with time windows (PVRPTW), in which the planning period is extended to several days and each customer must be served within a specified time window. Multi-dimension pheromone matrix is used to accumulate heuristic information on different days. Two-crossover operations are introduced to improve the performance of the algorithm. The effectiveness of IACO is evaluated using a set of well-known benchmarks. Some of the results are better than the best-known solutions. Results also show the IACO seems to be a powerful tool for PVRPTW.

Vehicle routing problem (VRP), related to many real-life applications, holds an important place in operation research (Laporte, 2009). Vehicle routing problem with time windows (VRPTW) is a well-known generalization of VRP where each customer must be served within a specified time window. VRPTW has been widely studied both in theoretical researches and practice applications in the last 20 years (Bräysy and Gendreau, 2005a, Bräysy and Gendreau, 2005b and Liu et al., 2009). In VRP or VRPTW, each customer is visited exactly once during the same planning period (a single day). Differing from standard VRP or VRPTW, the VRP with multiple periods (e.g. 1 week) is defined as PVRP. PVRP has extensive real-world applications, including the collection of waste, the distribution of equipment for intermodal operations, elevator maintenance and repair, and vending machine replenishment (Francis et al., 2008). Early heuristics for PVRP are proposed by Beltrami and Bodin, 1974 and Russell and Igo, 1979. Chao et al. (1995) presented a two-stage heuristic which consisted of initial solution construction phase and solution improvement phase. In the first phase, they assigned delivery day combinations to customers by solving an integer programming problem. Then, some strategies were used to improve the solution. Baptista et al. (2002) presented a case study of PVRP which was about the collection of recycling paper containers in the Almada Municipality, Portugal. Compared with classical PVRP, a novel feature of their case was that the frequency of visits to containers was considered as a decision variable in their model. Similarly, Francis et al. (2006) presented a special PVRP in which service frequency of customer was variable. They modeled the PVRP with service choice (PVRPSC) in which service frequency was a decision variable, and developed an exact solution method with heuristic variations for PVRPSC. Matos and Oliverira (2004) applied the Ant System in PVRP and presented a new updating strategy of pheromone information. Then, they tested their algorithm by a waste collection system involving 202 locations in the municipality of Viseu, Portugal. Other heuristics for PVRP were developed by Paletta, 1992, Paletta, 2002, Blakeley et al., 2003, Bertazzi et al., 2004, Drummond et al., 1999, Hadjiconstantinou and Baldacci, 1998 and Russell and Gribbin, 1991. The focus of this paper is on the period vehicle routing problem with time windows (PVRPTW), which is a generalization of PVRP. In PVRPTW, each customer can be served more than once within a specified time window during the planning period of several days. To the best of our knowledge, there is little literature to use heuristics for PVRPTW. Ant colony optimization (Dorigo et al., 1996) is an artificial intelligence procedure inspired from food-seeking behaviors of ant colonies in nature. It has been successfully applied to some classic compounding optimization problems, e.g. traveling salesman (Dorigo et al., 1996 and Stützle and Hoos, 2000), telecommunication routing (Schoonderwoerd et al., 1997), product design (Albritton and McMullen, 2007), etc. Recently, it has also been applied to solve VRP or VRPTW. Bullnheimer et al., 1997 and Bullnheimer et al., 1999 presented an Ant System to solve the vehicle routing problem; Bell and McMullen (2004) presented an ACO with multiple colonies for VRP; Yu et al., 2009 and Yu et al., in press presented an improved ACO, introduced ant-weight updating strategy and mutation operation, to solve VRP. Further researches were interested in ACO for VRPTW. Chen and Ting (2006) presented a hybrid algorithm combined ant colony system (ACS) and simulated annealing algorithm for VRPTW. Gong et al. (2007) presented a two-generation ACS for VRPTW. In their algorithm, the sub-tours were constructed during the child generation, while the feasible route was constructed during the parent generation. Tan et al. (2005) presented an improved ACS to solve VRPTW, in which two respective ant colonies were used to identify a multiple objective minimization. Zhu and Zhen (2009) presented a hybrid ACS with dynamic sweep algorithms for VRPTW. Qi and Sun (2008) proposed an ACS with a randomized algorithm for VRPTW. This paper aims to test the feasibility of ACO in PVRPTW. The remainder of the paper is organized as follows. In Section 2 we describe PVRPTW. In Section 3, ACO and some improvement strategies are presented. In Section 4, some computational results are discussed and lastly, the conclusions are provided in Section 5.

Period vehicle routing problem with time windows (PVRPTW) is a generalization of classical vehicle routing problem, in which the planning period is extended from a single day to several days and each customer must be served within a specified time window. This paper proposes an improved ant colony optimization (IACO) with multi-dimension pheromone information and two-crossover operations to solve PVRPTW. The effectiveness of the improved ant colony optimization is evaluated using a set of well-known benchmarks. Computational results show that the incorporation of multi-dimension pheromone information and two-crossover operations can improve the performance of ACO for PVRPTW. The main contributions of this paper to the literature can be summarized as follow: 1. This paper tests the feasibility of ACO for PVRPTW. 2. When applying IACO to solve PVRPTW, multi-dimensional pheromone information is the most suitable extension, which can be used to distinguish heuristic information during different days from previous searches. 3. Furthermore, the two-crossover operation always outperforms the one-crossoveroperation in the search quality, while the two-crossover operation need more computation time.4. The PVRPTW is a problem not much explored, but it has many possible applications in real world problems. This paper aims to formulate an approach and solution to stimulate the attention of other researchers.