1. Introduction

Vehicles routing and scheduling through a set of required services, could be counted as a key element in many distribution systems both in the private and public sectors. In vehicle routing problem (VRP), a fleet of vehicles supplies a set of geographically dispersed customers to construct optimal routes with a minimal cost regarding distance, time, and the number of vehicles. Each vehicle goes through a tour, and each tour starts from a depot going towards customers to satisfy their demands.

If the unknown attributes have been integrated with the constraints of VRP, the system has to incorporate changes and modify the scheduling to an appropriate one. This dynamically responding to requests is termed as dynamic VRP (DVRP), or on-line VRP, which is also well-known as real time VRP (RTVRP); noteworthy these titles are corresponded with the quality and quantity of the responding system’s capability.

As it is pointed out in reference[32], DVRP based on the degree of dynamism and objective function can be termed as weakly or moderately or strongly dynamic system. For example, a dial-a-ride problem with the number of immediate requests being quite low, in which requests are booked before the day of the trip, is considered to be a

weakly dynamic system ([19],[10],[58],[42]). Repair and mail services are counted as moderately dynamic routing systems ([23],[34]). In moderate systems, there is a need to have reaction to requests as soon as possible but not as fast as emergency cases that are known to be strongly dynamic systems ([24],[7]). Corresponding to the level of dynamism of DVRP, there are different optimizing methodologies such as heuristic and meta-heuristic methods. Our study utilizes the ant colony system (ACS) along with some quick heuristic methods to divert a vehicle away from its current destination to respond new requests.

1.1. The Motivations and Contributions

This paper has been inspired by the works done by references[23] and[39]. The main difference between our work and their studies is our account for some heuristic methods on ACS along with the scenarios of the DVRP. This is done to adapt the methodology with time restriction in order to find enough good solutions quick. In our method, new requests arriving during a slice time are listed and posted to the next closest time slice. During each time slice, a problem similar to a static VRP, but with vehicles having different capacities and starting locations, is traced.

This is a soft time window-based problem, in which requests should be responded dynamically. The future requests are not known, however the demands occur with Poison distribution function whereas the locations of requests are known. Regarding the order of the requests, vehicle are assigned to carry out them, therefore some requests may be postponed. This is the reason that we call it as a partially moderate DVRP.

The main contribution of our work is to develop a constructive structure to re-optimize routes for occurred events in the requests list. Although time window vehicle routing problems have been studied extensively, there is not a lot of ACS researched dedicated to solve DVRP (see Table 1). Insertion heuristic, tabu search, local search and genetic algorithm have attracted the most considerations in this field. Among them, the construction structure of ACS is well to solve routing kind problems; however the running time of this algorithm may seem high for DVRP. In this paper, we try to design an efficient ACS with setting appropriate parameters besides initial pheromone and increasing pheromone methodology. Moreover, neighborhood searches help us to reach feasible solutions quick. We prove that applied ACS is a suitable method for the proposed partially moderate DVRP.

Regarding the points have been cleared in[28] to have more logical judgments about the quality of the solutions, we make use of an alternative objective function in place of a distance-based objective function. Authors of[28] show the objectives of minimizing the make-span or the latency are inadequate since both will always be infinite. Thus, they consider the objectives of maxima and average flow time, which is the difference between the completion and release time. We use a combined idea of distance and flow time as the objective function.

Table 1. A summary of related works on dynamic vehicle routing problems References Problem Objective Solving technique [44] Stochastic model of dynamic vehicle allocation Maximizing the net revenue minus stockout costs Frank-Wolfe and heuristic splitting algorithms [34] Dispatching repair men Minimizing the travel cost Booking heuristic for routing and timing of customers [35] Dial-a-ride Minimizing the total driving time, waiting time, number of vehicles and deviation from expected service Insertion heuristic [23] Real-time routing and dispatching Minimizing the travel cost Parallel tabu search heuristic [28] Online dial-a-ride Minimizing the maximal/ average flow time REPLAN and IGNORE online heuristic strategies [24] Real-time ambulance relocation Maximizing the backup coverage demand Parallel tabu search heuristic [19] Dial-a-ride with dynamic and stochastic travel times Minimizing client inconvenience and service hours Heuristic algorithm coupled with a first-in-first-out (FIFO) assumption [10] Dial-a-ride with deterministic travels Minimizing the travel cost accommodating all requests Tabu search heuristic [2] Partially dynamic routing with stochastic customers Maximizing the number of serviced customers Multiple scenario approach [18] Dynamic routing and dispatching vehicles Minimizing delays and travel cost Heuristic assignment rules [37] Dynamic pickup and delivery with time windows Minimizing the travel cost accommodating requests Four waiting heuristic strategies [8] Routing a just-in-time (JIT) supply pickup and delivery system Minimizing the travel cost Column generation and tabu search [39] Dynamic routing Minimizing the travel cost Ant colony system [29] Dynamic and stochastic routing Minimizing the travel cost Scenario hedging heuristic [27] Dynamic routing Minimizing the travel cost Genetic algorithm [46] Dynamic pickup and deliver Minimizing the travel cost Insertion heuristics based on waiting and buffering strategies [58] Dial-a-ride under stochastic environments Minimizing the travel cost Heuristic scheduling based on local search strategy [6] Dynamic routing with time windows Maximizing the routing profit as the total revenue minus lateness and travel costs Granular local search heuristic [30] Routing with Dynamic Requests Minimizing the travel cost Multi-adaptive particle swarm optimization [42] Dial-a-ride Minimizing total routing costs Variable neighborhood search [31] Dynamic routing Minimizing the travel cost and insertion cost Particle swarm optimization and variable neighborhood search

1.2. The Applications of Model

The main purpose of our model is to apply for the repair, fuel distribution, courier and mail service systems or other moderate routing problems. Broken car rescue, appliance repair are counted as repair services that are evolved in real time. In the courier and email service systems, there are a limited number of vans going around a specified location to collect parcels in order to consolidate loads. Sometimes, dynamic pick-up requests have to be serviced in a same day. It is noteworthy that our study could be applicable for static version of VRP, too.

The application of this problem could be found in considering the realistic property, which is occurring continuously. There are different real problem categorizes that must be solved dynamically regarding time windows constraints. For example[41] applies soft time windows constraint on vehicle scheduling within airport logistic. Dial-a-ride system is another example, which gives transportation service to (handicapped or elderly) people between given origin and destination pairs. This system can be divided into the static model when trips are booked one day in advance ([10],[42]) or the dynamic models handling short notices ([35],[58]).

1.3. The Organization of paper

The rest of this paper is organized as follows. A review on the literature is presented in Section 2. The definition of the VRP and supposed dynamic strategy are provided in Section 3. The ACS procedure for real time responding to requests is presented in Section 4. Section 5 using Taguchi method takes into account the calibration of parameters and operators. A discussion on numerical results in comparing with other methods is given in Section 6. Lastly, conclusions and future work are presented in Section 7.

2. Literature Review

VRP falls into the combinatorial optimization and integer programming problem categories, being studied extensively in the past forty years. The research was done in [13] as the first paper on VRP has been followed by a significant number of scholars until the present time. Readers are referred to refernce[16], in which there is a comprehensive taxonomy of classifications and categories contributed by VRP.

The disparate structure of the literature of this problem makes it quite difficult to track developments on the subject. This subject covers several theoretical and practical disciplines from algorithm design to traffic management. Actually, VRP's facets encompass a spectrum from stochastic to deterministic areas and from static to dynamic issues. It could be said that time windows structure ([52],[40],[9],[3],[36],[38]), time horizon structure ([35],[10]), and backhauls ([14],[54]) are there general scenario characteristics of VRP.

There is a large portion of the literature on static VRP, which may be termed as traditional VRP. In the static VRP, the data such as the locations, load splitting, demand quantities, capacities of vehicles, request time, driving time, waiting time, and service time are known and deterministic ([49],[11],[43],[60],[38]). The complex structure of DVRP for scheduling orders to vehicles and vehicles to routes admits difficulties for finding feasible solutions, and this is the cause for lack of large number of researches in this field. With the enhanced computational capability offered in the 1990s and the enhancement in vehicle tracking, exchange media, and data storage, DVRP has been more common in the literature ([1],[2],[18],[39],[51],[6],[50],[30],[4]).

A variety of solution methodologies including heuristics, simulations and exact methods with regard to service strategies, relations between vehicles-customers along with supposing appropriate objective functions, have been developed to encounter DVRP models. Authors of[23] develop a parallel tabu search (TS) to find minimum cost of delay on service for presumed soft time windows. A survey on results obtained on different types of DVRPs can be found in[22]. References[26] and[39] develop different approaches of ant colony algorithm for DVRP. Reference[6] considers a granular local search heuristic for RTVRP. Note that partially dynamic vehicle routing problems may vary greatly in complexity according to the characteristics of dynamism, which have been classified as in[45] and[25].

The first DVRP study dates back to reference[44], which surveyed uncertainty in VRP with stochastic flows of vehicles. It could be said that stochastic routing is another attracting subject in VRP literature, in which supposing stochastic nature of events made it more close to real-world problems ([57],[56]).The concept of DVRP and RTVRP encompasses time window constraints on request nodes. Therefore, some DVRP fall under the stochastic vehicle routing problem category too([5],[21],[20],[29],[55],[17],[47]).The DVRP in which stochastic information about future request is known could be called dynamic and stochastic VRPs. In the current paper, we focus on the dynamic frame of VRP, in which routes could be changed regarding time windows. The ACS algorithm is used to solve the partially DVRP with stochastic characteristic of occurring future events with known demands and location.

3. The Dynamic Vehicle Routing Problem

The VRP can be described as a weighted graph-theoretic problem. Let indicates the graph, where are vertices, is the central depot, and the other nodes are N customers that have to be served. The arcs connecting vertices are represented with . There is a nonnegative demand for each node and a nonnegative cost associated with each arc which usually stands for the traveling distance from vertex to vertex j . Since , so the problem is called symmetric. In several practical cases, the triangular inequality holds, that is. The objective is to find a collection of K simple circuits with minimum cost satisfying the following constraints:

(1) Each circuit visits the depot.

(2) Each vertex is visited by exactly one circuit.

(3) The sum of the vertices’ demands visited by a circuit does not exceed the vehicle capacity.

Here, we explain how motions can be evaluated in time window constraints. The static mode can design routes by applying supposed ACS, but the key discussion is on dynamic routing. We survey the strategy aimed at discarding moves which are not most likely to yield any improvement. First of all, some descriptions about the basics of DVRP are given.

3.1. The DVRP Definitions

We consider the general case that some requests (of the pick up or delivery) could arrive randomly, just like courier distribution systems. Travel times are updated based on real time information; however, travel distances are kept constant in all experiments. All vehicles are assumed to be similar and there are capacity constraints for all of them, and the pre-defined number of vehicles is assumed to be sufficient to serve the average of the requests. There is no concentration of vehicles in a small area and the route loads are balanced. Moreover, when vehicles leave the depot, they do not have to go back to it, unless there is not enough capacity for servicing or when all the customers have been serviced. Notably, no service would be canceled even if delays are faced.

In the version of DVRP considered having time windows, each customer should be served within the earliest and latest service times giving as an interval. The demands for servicing new customers are generated at the nodes of the network according to a Poisson process. The travel times among nodes are known and deterministic, and each vehicle spends a known service time for each new coming customer. In this condition, part of the input is revealed to the dispatcher, while servicing the static requests. Given this, it is impossible for optimal routes to be produced in advance. At the best, what can be produced is to determine what action should be taken as a function of the state of the system.

Figure 1 shows an example of DVRP considered by time windows. The pre-planned customers and dynamic requests are depicted by grey and white nodes, respectively. The pre-planned routes are represented by solid lines. The thick arcs indicate the current positions of vehicles at the time the immediate requests are received. The new customers have to be inserted into the already planned routes with a minimal delay. Because of the time window constraints, some new requests, like might not be satisfied. Since our approach is not to reject requests, unsatisfied orders should be saved to be considered in the next work slices.

Figure 1. An example of DVRP with seven pre-planned customers and three immediate requests

Figure 2. An architecture of DVRP algorithm

Table 2. The List of symbols used in the DVRP

Some processes are known in advance before the start of the working day. As the day progresses, new orders arrive and the system has to incorporate them into an evolving schedule. The advancing technology allows for information to be obtained and updated in real time. The dispatching center can periodically communicate with the vehicles in order to assign them. When new requests occur, vehicles with enough capacities to satisfy the orders would be the candidate. Clearly, these vehicles have to satisfy pre-allocated requests, and so a new request would be assigned to a vehicle, if it does not violate the constraint of other pre-assigned requests. The hard restriction on time windows may cause loss of services; therefore, soft time windows are supposed. Consequently, the cost function of distribution for each circuit is defined by Eq. (1) below, as the total cost function of a routing solution is calculated by Eq. (2):

(1)

(2)

The cost function appeared in Eq. (1) contains total traveled distance as well as lateness penalty, which are measured regarding to either customers or the single depot. Table 2 lists the notation used in our DVRP model.

We divide a working day into time slices with equal length, where T is the length of the working day. It is crucial that information updating methodologies be sorted for assignment purposes, the accuracy have be done specially in the waiting section ([37],[46]). If there were no appropriate vehicle, the requests would wait in a queue for satisfying some pre-planned ones, until enough capacity for accomplishing requests in the queue is acquired. After completing a request, all new requests placed in the queue is checked, and the first request found to be appropriate for a remaining vehicle capacity is assigned, and the queue is sorted again. Determined orders have to be inserted in appropriate routes, and then appropriate modification should take place. A diagram for this process is shown in Figure 2 and described in the following algorithm. A pseudo code of the DVRP strategy is considered below.

Algorithm 1: The DVRP strategy

For each time slice, do

While there are new requests, do

Put new requests in a sorted queue.

For each request in the queue orderly, do

Consider appropriate vehicles with enough capacities as candidates.

Sort the candidates based on the cost function.

If it is feasible to insert new request in current time slice, then

Update the adaptive memory in each insertion.

Else

Put the request in the next slice.

End If

Apply the routing method (ACS/Insertion heuristic) and assign new requests.

Apply improving methods on the best solutions found.

New current solution= A complete feasible reconstructed solution.

End For

End While

End For.

3.2. The Insertion Heuristic

The insertion of new customers is quite a complicated task and consideration is needed either for partial or for full re-planning of the non-visited part of the routes. After determining the position, the circuits are broken into routes with the last station as the departure and the depot as a destination for each vehicle (route). Then, ACS, to be described in detail in the next section, would be applied to find a minimal cost for responding to requests. If there is more than one request, requests are processed in the order of their entrances.

Alternatively, there are different approaches in the literature to face with new customers. Our study compares ACS with the insertion idea for incoming orders arisen from the insertion heuristic, which was firstly proposed in[53].

We use some modifications on this method. Established upon this heuristic, the necessary and sufficient conditions for feasibility of inserting a customer, say , between and (as the last customer of kth vehicle and the depot, respectively) on a partially feasible route are:

(3)

(4)

The best feasible insertion place is searched in the emerging route phase to maximize the benefit derived from servicing the customer on the specified constructed partial route:

(5)

(6)

(7)

It is noteworthy that after insertion, would be updated. The involved parameters in the above insertion heuristic affect the best feasible place for an un-routed customer. Provision of service to a customer is dependent on a weighed combination of distance to the place and time window violation. A pseudo code of the algorithm can now be given.

4. The Hybrid Ant Colony System

Here, we describe a methodology for finding the shortest path by using ACS in order to find enough good solutions in real time events. The proposed method hybridizes the mechanism of ACS and some updating and exploration searches. Discussion on ACS as an applicable algorithm for combinatorial optimization problems can be found in[15], but here we give some explanations about the current approach on this well-known meta-heuristic algorithm. The notations used in the ACS algorithm are presented in Table 3.

Table 3. The List of symbols used in the ACS

A pseudo code of the hybrid ACS is given below.

Algorithm 2: The hybrid ACS process

Initialization

Set best routes, pheromone and data structure as initial solution.

While the stopping criterion is not met, do

For each ant k , do

Construct a solution .

Update the tabu list, pheromone, and data structure (local updating).

End For

Neighborhood search {mutation operator, cross, and 2-opt exchanges}.

New current solution = The best (non tabu) solution in the neighborhood.

If the current solution is better than the best so far, then

The best overall solution = The current solution.

End If

Update the tabu list, pheromone, and data structure (global updating).

End While

Return the best overall solution.

4.1. The Initial Solution

The minimum travel time solution can include a number of vehicles more than the one obtained by a solution with a minimal number of vehicles (see[20]). A heuristic method such as the one gave in[53] may be used to minimize the number of vehicles. Generally, minimizing the number of vehicles is unsuitable for DVRP, because it leaves a low residual capacity for each vehicle to accommodate dynamic requests. Since time being a critical element in DVRP, we thus prefer to use all available vehicles to form the first seed of routes. Two different heuristic scenarios are surveyed to find the initial solution for known customers. Both utilize a seed to go on finding routes. One of them lets the vehicles service customers as much as possible and this is done based on using the nearest neighbor to the last serviced customer. In this way, some vehicles service a large number of customers, while some others serve none.

Another scenario forms the routes around the seed in finding a suitable customer near the last serviced customer for each vehicle in order. The former scenario leads to finding better routes having lower costs. Because of the necessity for scattering vehicles in the environment in order to have quick reactions to the incoming requests, it is logically better to use the latter scenario for DVRP. Therefore, at the beginning of the work shift, each known customers is assigned to a pre-defined number of vehicles.

To determine seeds of the routes, customers are assigned to vehicles using Eq. (1) as a cost function. Initially, a seed of routes is formed using known customers with minimum cost with respect to a single depot. When the size of the seed equals the number of routes, un-routed customers are inserted into these routes. This is done based on the cost incurred regarding the last inserted customer on each route. The insertion process is repeated until all static customers are visited.

4.2. The Neighborhood Searches

Since a good structure is based on a robust infrastructure, we try to find good initial solutions. Hereby, accomplishing ACS, we used some additional heuristics. This was done by using some neighborhood searches over the initial solution to restrict the exchanges to consecutive customers in the routes. Three neighborhood structures were used to find new better solutions in any iteration. The mutation operator, cross, and 2-opt exchange heuristics played the main roles in searching the solution space.

The idea of the mutation operation is to randomly mutate the route and then produce a new solution that is not far from the original one. The steps for the mutation operation are as follows:

(1) Select the two routes from the parent solutions and determine the mutating point for each one.

(2) Exchange the work stations in the different tours and generate the child solution.

(3) Ensure that the child solution is counted as a local optimum.

As stated in[23], among different exchanging methods, the cross exchange can yield better results than other neighborhood searches. In this case, two segments of different lengths are removed from the current solution. Then, each segment is reinserted at the location with the smallest detour. In other words, an arc of each route is deleted and two other arcs are inserted such that each resulting route has customers of both original routes.

The 2-opt exchange can be applied to improve the tours. This move deletes two arcs from a route and adds two new ones to the same route (see[12]). This means that some randomized possible pair-wise exchanges of customer locations visited by individual vehicles are tested to find out whether there would be any improvement in the objective function.

The indicated neighborhood search is used in the dynamic part of the problem leading to some chances for new customers to be designated to more appropriate routes. These exchanges may create invalid solutions, in which case routes should be modified to the nearest valid solution. After changes made to reconstructed routes, we modify routes to feasible solutions.

4.3. Pheromone Updating of ACS

An adaptive learning technique in ACS is to update the pheromone to cause improvement of new solutions. The colonies exchange information through pheromone updating. This process in ACS is conducted by reducing the amount of pheromone on all edges in order to simulate the natural evaporation of the pheromone and to guarantee that no path becomes too dominant in local updating, Eq. (8), and insists on the best solution by maximizing the pheromone trail value in global updating, Eq. (9):

(8)

(9)

As it is explained in[20], the value , where is the initial solution produced by a greedy heuristic, can make good initial pheromone trails on the arcs.

In addition, we utilize the idea of ant-weight strategy rule for the pheromone increment updating[59]. The ant-weight strategy consists of two components: the global pheromone increment and the local pheromone increment. This updating method appropriates additional pheromone depending on the solution quality or the contribution of each link to the solution. The strategy is then written to be:

(10)

(11)

Because both the global and local features of a solution are considered in this pheromone updating procedure, the assigned additional pheromone is directly responsible for the enhanced quality of routes. Moreover, the runs this algorithm has shown that a second update greatly improves the system’s performance. We applied this strategy for finding more favorable routes having more pheromones to produce accurate direct information for subsequent searches.

4.4. The Probability Function of ACS

It can be said that pheromone trails give a measure of how much an arc is desirable to be inserted in a solution. In other words, these trails are used for exploration and exploitation. Based on the characteristic of ACS to select the next station j , the ant k at the current position of customer uses the probabilistic Eq. (12), as given below:

(12)

where, represents a random selecting method according to the probabilistic distribution of Eq. (12), as given below:

(13)

Although is usually counted as a static value, but in DVRP, it can be changed with respect to the corresponding time and distance of each arc, and so we have defined it as the inverse of distribution cost , which incorporates the combination of distance and travel time for each arc in each route. The value of the pheromone trail is dynamically changed.

5. Calibration of the Parameters and Operators

Clearly, the values of parameters involved in the ACS algorithm directly or indirectly affect the quality of the final solution, and so control is needed for the result to be reliable. In order to determine the best combination of parameters for ACS, Taguchi’s method is used[48]. This method combines design of experiments and optimization of the control parameters based on the orthogonal array experiments and optimal settings of control parameters giving much reduced variance for the experiments.

Exploring all parameter states is expensive and so selecting a candidate list as a representative for the search would be appropriate. We choose control factors including the number of ants , the influence of the pheromone , the visibility , the pheromone decay , and the probability exploration , which are respectively symbolized by A, B, C, D, and E. For each parameter, three quantities are investigated as shown in Table 4.

Table 4. The involving factor levels in DACS

Table 5. The modified orthogonal array L18 Scenario Control Factor Level A B C D E 1 A(1) B(1) C(1) D(1) E(1) 2 A(1) B(2) C(2) D(2) E(2) 3 A(1) B(3) C(3) D(3) E(3) 4 A(2) B(1) C(1) D(2) E(2) 5 A(2) B(2) C(2) D(3) E(3) 6 A(2) B(3) C(3) D(1) E(1) 7 A(3) B(1) C(2) D(1) E(3) 8 A(3) B(2) C(3) D(2) E(1) 9 A(3) B(3) C(1) D(3) E(2) 10 A(1) B(1) C(3) D(3) E(2) 11 A(1) B(2) C(1) D(1) E(3) 12 A(1) B(3) C(2) D(2) E(1) 13 A(2) B(1) C(2) D(3) E(1) 14 A(2) B(2) C(3) D(1) E(2) 15 A(2) B(3) C(1) D(2) E(3) 16 A(3) B(1) C(3) D(2) E(3) 17 A(3) B(2) C(1) D(3) E(1) 18 A(3) B(3) C(2) D(1) E(2)

The total degree of freedom for a supposed parameter with three levels is equal to 5×2=10, and so the fittest orthogonal array is L₁₈. The modified orthogonal array L₁₈ for our case is shown in Table 3. Each test scenario of Table 5 was used to run test C101 of the Solomon benchmark problems four times. The approach is also effective on other instances of the Solomon benchmark problems, as observed in our further experiments not shown here for the sake of brevity.

Further details on experimental design procedure in Taguchi method can be found in[48]. Taguchi's signal-to-nois e ratio, which is log functions of desired output, serves as objective function for optimization, and helps in data analysis and prediction of optimum results. The ratio representing the magnitude of the mean of a process compared to its variation as introduced by Taguchi is given by the following formulas:

(14)

(15)

where, y is an indicator for the result of repeating each experiment and n is the number of repetitions. The mean of is exhibited in Figure 3, and Figure 4 confirms the level for each factor by using the mean of normalized objective function as a common performance measure.

The mean square deviation (MSD) and ratio are related to each other, and so for our study the larger is better. To achieve better results, the following setting should be made for the factors: level 3 for factor A, level 3 for factor B, level 1 for factor C, level 2 for factor D, and level 2 for factor E. The analysis for parameter setting S/N ratio is done with ANOVA as exhibited in Table 6. With 95% confidence level, the level of factor B is not found to be considerable among the indicated levels here.

Figure 3. The mean of ratio for each level of the ACS factors

Figure 4. The mean of normalized objective function for each level of the ACS factors

Table 6. ANNOVA for the       ratio Factors D.F S.S. M.S. F Percent X Cumulative A 2 0.017496987 0.008748493 1.807165366 2.5992682 2.5992682 B 2 0.183068861 0.09153443 18.90815288 57.668596 60.267864 C 2 0.027089484 0.013544742 2.797920475 5.78974 66.057604 D 2 0.013673097 0.006836548 1.412217261 1.3274396 67.385043 E 2 0.025445336 0.012722668 2.628105677 5.2428951 72.627938 Error 7 0.033887023 0.004841003 Total 17 0.300660788 0.138227886

Figure 5. An example of re-optimized route for incoming customers as time progresses

According to the obtained results, the following parameter settings have shown to be suitable for ACS calibration: and for the parameters independent of the ACS process .

In addition to the parameter setting for ACS, the parameters of the insertion method are set as We used the same share of time and distance for our method.

6. Numerical Results and Discussion

The 56 benchmark problems of Solomon’s instances composed of six different problem types C1, C2, R1, R2, RC1,and RC2 were used to evaluate the developed ACS for DVRP. These problems contain between eight to twelve 100-node problems. The locations of customers in problem set R are generated as uniformly distributed random numbers in a square[0, 100] ×[0, 100]. For the test set C, the customers whose time windows are generated based on a known solution, are placed in clusters, and the test set RC is a combination of randomly placed and clustered customers. There are narrow time windows and small vehicle capacities for sets of type 1, and large time windows and large vehicle capacities for sets of type 2. Therefore, the solutions of type 2 problems have very few routes and significantly more customers per route.

We supposed that about 40% of requests of these benchmarks appeared as dynamic requests depending on the order of the request in the original instances. The entrance rate was adapted with the length of the working day T to consider each one of the 100 requests. The length of working day was set to the due date vehicles needed to return to the depot. Event manager was set to handle the immediate requests during the day after the advancing requests were serviced. We considered this uniform rate, because this seemed to be an intuitively correct approach for the performance of the dynamic system. For instance, Figure 5 graphically displays the entrance of static and dynamic customers for vehicle number 1 of C101 test problem. The route is extended from to as the left and right subplots show respectively.

Experiments on the algorithms were made in MATLAB^® 7.6.0 (R2008a) environment, on a PC with 2.0GHz Intel Core^® 2 Duo processor and 2GB RAM. Each test was conducted for four times, and the solution for each problem type is reported as the mean of the obtained results.

First, the comparisons of three classes of Solomon’s instances are reported in Tables 7-9. These tables respectively represent the mean of the costs obtained by applying different neighborhood search methods on ACS-DVRP and insertion for the R, C and RC problem sets. The first column in each method titled COST is the result obtained by cost function, and the second column named DIST is the traveled distance. Figure 5 shows suitable operators for the problem with respect to distance or cost function. For example, the mutation operator is more appropriate for type 2 tests, and 2-Opt exchange is usually a good selection for type 1 tests. Our study considers cost functions located in the left side of the figure. Eventually, ACS-DVRP is suggested for developing a DVRP with the supposed attributes.

Table 7. The results of comparing heuristic for test problems R Problem R1   R2 Methodology ACS-DVRP Insertion Heuristic   ACS-DVRP Insertion Heuristic Function COST DIST COST DIST   COST DIST COST DIST Mutation 10396.324 3565.0306 10875.463 3676.781   8257.5545 3450.9864 8509.0182 3516.1529 Cross Exch. 9901.3577 3600.8199 10267.272 3823.6443   8488.9956 3548.44 8625.7583 3599.6925 2-Opt 9975.117 3509.7503 10371.507 3667.4862   8702.7548 3629.4199 9146.5268 3816.2552

Table 8. The results of comparing heuristic for test problems C Problem C1   C2 Methodology ACS-DVRP Insertion Heuristic   ACS-DVRP Insertion Heuristic Function COST DIST COST DIST   COST DIST COST DIST Mutation 19306.266 4222.5108 19733.384 4298.6558   17616.565 3909.6282 17811.261 3978.4795 Cross Exch. 19277.058 4161.7924 19791.779 4329.2819   17776.285 3979.3309 17852.827 4061.8004 2-Opt Exch. 19154.217 4211.7042 19571.007 4391.1376   17815.752 3981.7287 18240.791 4151.0525

Table 9. The results of comparing heuristic for test problems RC Problem RC1   RC2 Methodology ACS-DVRP Insertion Heuristic   ACS-DVRP Insertion Heuristic Function COST DIST COST DIST   COST DIST COST DIST Mutation 14173.928 4614.7092 14639.637 4769.1463   10745.27 4643.3659 11076.434 4747.3458 Cross Exch. 14453.602 4612.2534 15312.951 4811.0675   11114.58 4714.9816 11401.118 4923.7998 2-Opt Exch. 14543.764 4599.3484 14872.385 4681.7297   10954.945 4657.4057 11240.504 4853.5573

Figure 6. The analysis for different operators on DVRP

Table 10. The comparisons of ACS and insertion heuristic with different sizes of DVRP

It appears that the obtained means of cost and distance for the test 2 set are better than the ones for the test 1 set. The reason may relate to narrow time windows effecting on the cost function and certainly on the distances.

The ACS-DVRP is compared with insertion heuristic for some extended Solomon’s VRPTW instances. Table 10 shows comparison for min, max and mean for four runs of each scenario. Totally, the results obtained by ACS-DVRP are better than insertion heuristic’s. This may be explained by the fact that the population-based structure of ACS, avoiding local optimum, can provide more direct searches in constructing and re-optimizing routes. The insertion method utilizing a greedy approach, searches new routes that leads to more costly solutions. Fairly, the results show that the cost function can be a more suitable measure than the distance function.

7. Conclusions

In this paper, we proposed an ant colony system for dynamically responding requests in the vehicle routing problem. We used ACS besides neighborhood searches including mutation, cross and 2-opt exchange heuristics. As the procedure progresses, new solutions are created from the routes associated with previous solutions based on the defined objective function. The experimental results show that our hybrid ACS acts well for the supposed DVRP.

It is important to notify that the approach is essentially domain-independent, and we expect that many other dynamic applications may benefit from this technique. Since time is a significant note on real time strategies, application of quick search strategies other than ACS are worth investigating. As further study, a simulation based study could be helpful to evaluate events for the considered problem. In addition, instead of certain probability distribution, uncertainty could be supposed, which there are rare studies in this regard such as reference[33].

ACKNOWLEDGEMENTS

The authors would like to thank Professor Gilbert Laporte for his valuable comments that helped authors improve the paper.