More

Cost_Matrix Distance: Vehicle routing problem!

Cost_Matrix Distance: Vehicle routing problem!


I'd like to calculate the "real distance" between one source and many targets, such as we do in the "vehicle routing problem", in order to get the matrix distance at the end.

after using the osm2po, and loading the topology into QGIS, and installing pgrouting plugin:

How could I do this cost matrix with the Pgrouting/QGIS? to get a result such as in like in points are {1,2,3}, the problem is asymetric

1---1=0 1---2=2 1---3=4 2---1=5 2---2=0 2---3=21 3---1=5 3---2=4 3---3=0

knowing that almost the functions found in Pgrouting are for calculating the shortest paths, and the function "tsp_euclid" doesn't return a result in my case.


Vehicle Coordinated Strategy for Vehicle Routing Problem with Fuzzy Demands.

The vehicle routing problem (VRP) was first proposed by Dantzig and Ramser [1]. The VRP has since been the topic of many operational studies. VRP consists of designing efficient routes to serve a number of nodes with a fleet of vehicles. Each node is visited exactly once by one vehicle. The activity of the vehicle is bounded by certain constraints. Each vehicle starts at the depot and returns to the same depot after completing its task. Most VRP studies employ the vehicle uncoordinated strategy that is, there is no coordination between the vehicles, and each vehicle completes only its own task. There are many significant VRP results based on this case, including those of Clarke and Wright [2], Solomon [3], Laporte [4], Figliozzi [5], Sprenger and Monch [6], Pillac et al. [7], Kou et al. [8], and Kou et al. [9].

The vehicle routing problem with fuzzy demands (VRPFD) is an extension of the VRP that is, the demand of each node is uncertain, subjective, ambiguous, and/or vague [10]. The VRPFD is widely employed for many real applications due to their numerous uncertainties, including garbage collection systems, product recall systems, and raw milk collection systems (collecting raw milk from dairy farmers for milk powder production enterprises). There are also several classical studies that refer to the VRPFD, such as Bertsimas [11], Cao and Lai [12], Kuo et al. [13], Kou and Lin [14], Kou et al. [15], Allahviranloo et al. [16], and Hu et al. [17]. The VRPFD typically assumes that the real value of a node's demand is known when the vehicle reaches the node, whereas the vehicle's route is planned in advance. After serving v nodes, the vehicle might not be able to service the V +1 node once it arrives due to insufficient capacity. In such situations, if the vehicle uncoordinated strategy is employed, the vehicle must return to the depot and unload what it has picked up thus far and then return to the node where it had a "service failure" and continue to serve the remaining nodes. Thus, "additional distance" and "additional unloading times" are introduced due to the "service failure." However, there are also vehicles with surplus capacity after completing their own tasks, introducing "waste capacity." All of these cases result in increasing logistics cost. To the authors' knowledge, few researchers have addressed the problem of minimizing the "additional distance" and "waste capacity," let alone "additional unloading times," in the VRPFD.

Thus, in this paper, the fuzzy reasoning constrained program model for VRPFD is formulated, and the hybrid ant colony algorithm is designed to minimize total travel distance. In particular, the two-vehicle-paired loop coordinated strategy (TVPLCS) is presented to reduce the "additional distance," "additional unloading times," and "waste capacity" caused by the service failure due to the uncertain demands. Finally, numerical examples are presented to demonstrate the effectiveness of the proposed approaches.

The remainder of this paper is organized as follows. In Section 2, the fuzzy reasoning constrained program model for VRPFD is formulated. In Section 3, we design a hybrid ant colony algorithm for VRPFD. In Section 4, in particular, we present the TVPLCS to minimize the "additional distance," "additional unloading times," and "waste capacity". In Section 5, we give numerical examples to demonstrate the effectiveness of the proposed approaches. Finally, we summarize the contributions of this paper.

2. VRPFD Assumptions and Model

2.1. VRPFD Assumptions. In this paper, the VRPFD assumes that there is only one depot denoted by 0, and there are n nodes with fuzzy demands served by m vehicles. The locations of the depot and nodes are known. The fuzzy demand of each node i is uncertain and only characterized by a triangular fuzzy number [D.sub.i], [D.sub.i] = ([d.sub.i1], [d.sub.i2], [d.sub.i3]). [d.sub.i1] is the minimum of the demand of node i, [d.sub.i3] is the maximum of the demand of node i, and [d.sub.i2] is the most likely value. The distance [c.sub.ij] between nodes i and node j is known. Each node is served exactly once by one vehicle. For simplicity, the capacity Q of each vehicle is the same, and the activity of the vehicle is only bounded by capacity constraints. Each vehicle starts at the depot and returns to the same depot after completing its task. The objective is to design a set of vehicle routes that minimizes the total logistics costs.

2.2. Deciding whether the Vehicle Serves the Next Node or Returns to the Depot. When the demand of each node is deterministic, it is easy for us to decide whether the vehicle is able to serve the next node after serving v nodes. However, while the demand at each node is uncertain and only characterized by a triangular fuzzy number [D.sub.i] = [d.sub.i1], [d.sub.i3]), it is difficult for us to decide whether the vehicle should serve the next node v + 1 or return to the depot. We only know that the greater the vehicle's remaining capacity and the lesser the demand at the next node, the greater the vehicle's "chances" of being able to serve the next node. In this paper, we solve this problem by triangular fuzzy number theory proposed by Liu [23], which described as follows.

The membership function of triangular fuzzy number D = ([d.sub.1], [d.sub.2], [d.sub.3]) is defined as

[mathematical expression not reproducible]. (1)

Let pos <[epsilon]>be the occurrence possibility of event e. For triangular fuzzy number A = ([a.sub.1], [a.sub.2], [a.sub.3]) and B = <[b.sub.1], [b.sub.2], [b.sub.3]>, pos is defined as

[mathematical expression not reproducible]. (2)

Now, we can deduce that the occupied capacity QV0 of the vehicle which had served v nodes is

[Q.sub.vo] = [v.summation over (i=1)][D.sub.i] = ([v.summation over (i=1)][D.sub.i1], [v.summation over (i=1)][D.sub.i2], [v.summation over (i=1)][D.sub.i3]). (3)

Also, the capacity Q of each vehicle can be presented as a triangular fuzzy number Q = (Q, Q, Q). So, the remaining capacity [Q.sub.vr] of the vehicle is

[Q.sub.vro] = Q - [Q.sub.vo] = (Q - [v.summation over (i=1)][D.sub.i3], Q - [v.summation over (i=1)][D.sub.i2], Q - [v.summation over (i=1)][D.sub.i1]) = ([Q.sub.vr 1], [Q.sub.vr 2], [Q.sub.vr 3]). (4)

Thus, the possibility pos([D.sub.v+1] < [Q.sub.vr]), which means that the demand of node v + 1 is less than the remaining capacity, is

[mathematical expression not reproducible]. (5)

Let P* [member of] [0,1] be the decision maker's preference. A large value of P* indicates that the decision maker is risk averse, and the decision maker aims to ensure service. In this case, P* [greater than or equal to] 0.6. The possibility of "service success" is relatively high. In contrast, a small value of P* means that the decision maker has an insatiable appetite for risk and tries to serve more nodes with each vehicle. In that case, P* [less than or equal to] 0.5. The possibility of "service success" is relatively low.

Now, after serving v nodes, we can make a decision whether the vehicle should serve the next node v + 1 or return to the depot 0. The decision was made as follows.

If pos([D.sub.v+1] [less than or equal to] [Q.sub.vr]) [greater than or equal to] P*, the vehicle should serve the next node v + 1 else, the vehicle should return to the depot 0.

2.3. VRPFD Model. The notations used in the formulation of the VRPFD are described as follows.

i: node index (i = 0 stands for the depot).

S: nonempty proper subset of the set N.

[D.sub.i]: fuzzy demand of each node i, [D.sub.i] = ([d.sub.i1], [d.sub.i2], [d.sub.i3]).

[c.sub.ij]: distance between node i and node j.

Q: capacity of the vehicle.

[P.sup.*]: decision maker's preference, [P.sup.*] [member of] [0, 1].

The decision variables used in the formulation of the VRPFD are described as follows:

Thus, the fuzzy reasoning constrained program model of the VRPFD is mathematically formulated as follows:

min [m.summation over (k=1)] [n.summation over (i=0)] [n.summation over (j=0)] [c.sub.ij] [x.sub.ijk] (6)

Subject to pos ([summation over (i[member of]N)] [D.sub.i] [y.sub.ik] [less than or equal to] Q) [greater than or equal to] [P.sup.*], [for all]k [member of] K (7)

[summation over (k[member of]K)] [y.sub.ik] = 1, [for all]i [member of] N (8)

[summation over (i[member of]N)] [x.sub.ijk] = [y.sub.jk], [for all]j [member of] N, k [member of] K (9)

[summation over (j[member of]N)] [x.sub.ijk] = [y.sub.ik], [for all]i [member of] N, k [member of] K (10)

[summation over (j[member of]N)] [x.sub.ijk] = [summation over (j[member of]N)] [x.sub.jik] = [y.sub.ik], [for all]i [member of] N, k [member of] K (11)

[summation over (k[member of]K)] [y.sub.0k] = m (12)

[summation over (j[member of]N)] [x.sub.0jk] = [summation over (i[member of]N)] [x.sub.i0k] = 1, [for all]k [member of] K (13)

[summation over (k[member of]K)] [summation over (i[member of]S)] [summation over (j[member of]S),j[not equal to]i] [x.sub.ijk] [less than or equal to] [summation over (j[member of]N)] [x.sub.jik] = [absolute value of (S)] - 1, [for all]S [subset] N (14)

The object of the proposed VRPFD is to minimize the total distance. Constraint (7) ensures that all nodes are served within the vehicle's capacity at the values of the decision maker's preference. Constraint (8) ensures that each node is visited by one vehicle. Constraints (9) and (10) define the relationships between [x.sub.ijk] and [y.sub.ik], respectively. Constraint (11) guarantees that a vehicle must enter and leave each node exactly once. Constraint (12) ensures that at most m vehicles are used. Constraint (13) ensures that vehicle routes start from the depot 0 and terminate at the same depot. Constraint (14) represents the subtour elimination constraint where |S| stands for the cardinality of set S.

3. Hybrid Ant Colony Algorithm for VRPFD

The ant colony algorithm (ACA) is one of the most popular swarm-inspired methods in the field of computational intelligence. The first ACA was developed by Clolrni et al. [24]. It was successfully applied to the traveling salesman problem. The first ant system for the VRP was proposed by Bulleneimer et al. [25]. Doerner et al. [26] further improved this ant colony system using a savings-based heuristic. Recently, ACA has been applied to the VRP with different constraints, for example, Ellabib et al. [27], Gajpal and Abad [28], Yu et al. [29], and Fleming et al. [30]. By looking at success of above hybridised ant colony algorithms on VRP, we decided to develop hybrid ant colony algorithm (HACA) for VRPFD too.

Let [OMEGA] be the set of all candidate nodes in the dataset, let U(h) be the set of nodes yet to be served by ant h, and let I(h) be the set of nodes already served by ant h.

3.1. Transfer Probabilities. The probability [p.sup.h.sub.ij] that ant h chooses to serve node j having served node i is given by

[mathematical expression not reproducible], (15)

where [[tau].sub.ij] is the pheromone density of edge (i, j) [[eta].sub.ij] is the visibility of edge (i, j) [alpha] is the relative influence of the pheromone trails and [beta] is the relative influence of the visibility.

3.2.1. Local Pheromone Updating Rule

Definition 1 (ant attraction). The ant attraction [partial derivative]/[chi] of edge (i, j) is the ratio of number [partial derivative] of ants that have travelled edge (i, j) to the number [chi] of ants that have visited node i.

Each ant leaves constant quantity [theta] of pheromone on the edge it travels, and larger ant attraction [chi][theta] of edge (i, j) results in greater amount of ant travel on edge (i, j). Thus, more frequent local pheromone updating will result in a larger pheromone quantity [[tau].sub.ij] between all edges. The global searching of the ACO algorithm represents a handicap. To address this problem a local pheromone updating rule has been designed.

Let [[chi].sub.h] be the number of ants that visited node i before arrival of ant h at node i, and let [[partial derivative].sub.h] be the number of ants that travelled edge (i, j) before ant h travelled edge (i, j). The local pheromone update quantity of edge (i, j) caused by ant h can be calculated as

[mathematical expression not reproducible]. (16)

Let [[tau].sup.h.sub.ij](t) be the local pheromone quantity of edge (i, j) before updating let [[tau].sup.h.sub.ij](t + 1) be the local pheromone quantity of edge (i, j) after updating and let [rho] be the pheromone volatilization coefficient. Then, the local pheromone updating rule can be defined as

[[tau].sup.h.sub.ij](t+1) = [rho] x [[tau].sup.h.sub.ij](t) + [DELTA][[tau].sub.ij](t), [for all]i, [for all]j, i [not equal to] j, (17)

[DELTA][[tau].sub.ij](t) = [m.summation over (h=1)] [DELTA][[tau].sup.h.sub.ij](t). (18)

3.2.2. Global Pheromone Updating Rule. If ant h has already served all n nodes, the global pheromone updating rule is employed. It is defined as

[[tau].sub.ij] (t + n) = (1 - [rho]) x [[tau].sub.ij] (t) + [DELTA][[tau].sub.ij](t), (19)

[DELTA][[tau].sub.ij] (t) = [m.summation over (k=1)][DELTA][[tau].sup.h.sub.ij] (t). (20)

3.3. The Steps of HACA. The steps of the proposed HACA are depicted below.

Step 1 (algorithm initialization). (1) Set the values of the current iteration number nc, the maximum iteration number max ir, the capacity value Q, the ant number m, and the decision maker's preference [P.sup.*]. (2) Set all ants at the central depot 0, and let each ant start from the depot. (3) Let [Q.sub.vo] = 0 be the initial occupied load of ant h, and the remaining capacity [Q.sub.Vr] = Q - [Q.sub.vo].

Step 2 (route construction). (1) Calculate the transfer probability [p.sup.h.sub.ij]. (2) Select node j according to the sequence of [p.sup.h.sub.ij] arranged in decreasing order. (3) If pos([D.sub.j] [less than or equal to] [Q.sub.Vr]) [greater than or equal to] [P.sup.*], j [member of] U(h), ant h must move to node j from the current node i, and the current node of ant h is changed to be j, j [not member of] U(h), j [member of] I(h), and the occupied load [Q.sub.vo] = [Q.sub.vo] + [d.sub.j] otherwise, ant h should return to the depot, [Q.sub.vo] = 0, and move to the next node j. (4) Repeat this selection until U(h) = [phi].

Step 3 (pheromone updating). If U(h) = [phi], that is, ant h has already served all n nodes, the global pheromone updating rule is employed otherwise, the local pheromone updating rule is employed.

Step 4 (judgment). If the total number of searching ants is smaller than m, return to step 2 otherwise, find the best solution by the path set L = <[L.sub.1], [L.sub.2], . [L.sub.m]>obtained with I(h).

Step 5 (the 2-opt local search). (1) The obtained route is broken at random into three segments. (2) The middle segment must not contain the depot. (3) The route is then reconstructed by reversing the middle segment. (4) The route is updated whenever there is an improvement. (5) The process is repeated until there is no further improvement in the solution [28]. (6) If the new solution is better than the current solution, the new solution will replace the current solution.

Step 6 (termination rule of the algorithm). If nc < max ir, nc = nc + 1, return to step 2, and repeat the above steps otherwise, terminate the HACA.

4. Two-Vehicle-Paired Loop Coordinated Strategy

As mentioned above, the VRPFD typically assumes that the "actual" value of a node's demand is known when the vehicle reaches the node, and the vehicle route is planned in advance. After serving v nodes, a vehicle might not be able to service the v +1 node once it arrives due to its insufficient capacity. In such situations, if the vehicle uncoordinated strategy is employed, the vehicle must return to the depot, unload what it has picked up thus far, return to the node where it had a "service failure," and continue to service the remaining nodes (e.g., in raw milk collection systems). Thus, "additional distance" and "additional unloading times" are introduced due to the "service failure" (Figure 1). In contrast, there are also vehicles with surplus capacity after completing their own tasks thus, "waste capacity" is created. All of these cases increase the logistics costs. To the authors' knowledge, few studies have considered the problem of how to effectively minimize the "additional distance" and "waste capacity," let alone reduce "additional unloading times," in the VRPFD.

After the optimal routes are obtained by the HACA (it is assumed that each route only served exactly by one vehicle), the two-vehicle-paired loop coordinated strategy (TVPLCS) is presented to minimize the "additional distance," "additional unloading times," and "waste capacity" in the VRPFD. The essence of the TVPLCS is that the vehicle with "surplus capacity" must help the vehicle with "insufficient capacity" according to the specified coordination rules after finish its own assigned task. The coordination rules of the TVPLCS are described as follows.

Coordination Rule 1. Assume that there are m planned vehicle routes and one depot 0 in two-dimensional coordinates. Put the depot on the origin of the two-dimensional coordinates. Starting from y-axis, divide the 2 adjacent routes into a coordinated group according to clockwise rotation (Figure 2). If the number of the routes is odd, there is one remaining route which is not assigned, and the vehicle will complete its own assigned task.

Coordination Rule 2. Each vehicle of the same coordinated group should finish its own assigned task first, and each vehicle first serves its "outer" nodes and then its "inner" nodes (Figure 3(a)). In this manner, if a vehicle has a "service failure," the "failure nodes" are near the other vehicle in the same coordinated group, thus promoting coordination between the two vehicles (Figure 3(b)).

Coordination Rule 2. If a vehicle completes its own task and has no surplus capacity, it should return to the depot and inform the other vehicle of its "task status."

Coordination Rule 4. If a vehicle completes its own task, has surplus capacity, and does not receive information from the other vehicle, the vehicle should wait and inform the other vehicle of its "task status" (Figure 4(a)). If the vehicle receives information from the other vehicle that the other vehicle is completing its own task, the first vehicle should return the depot (Figure 4(b)). If the vehicle receives information from the other vehicle that the other vehicle cannot complete its own task, the first vehicle should go to the node where the other vehicle had a "service failure" and continue to serve the remaining nodes. If the vehicle completes the remaining tasks, it should return the depot and inform the depot (Figure 4(c)) otherwise, the vehicle should return to the depot and inform the depot of its "remaining task status" (Figure 4(d)).

Coordination Rule 5. If all vehicles of all coordinated groups have returned to the depot and there are "remaining nodes" because of "service failure," the "remaining nodes" will be served by the vehicles of the second scheduling optimization, and the vehicle coordinated strategy will also be employed in the second service (Figure 5).

There are also some deficiencies in the TVPLCS, such as the "waiting" and "informing" between the two vehicles. "Waiting" means that if the vehicle completes its task and has surplus capacity, it must wait for the other vehicle's information. It may wait a long time due to different traffic circumstances, thus increasing the time cost. "Informing" means that when the vehicle completes its task, it must inform the other vehicle of its "task status." The "informing" problem can be easily solved using the advanced communication technology now available.

The program for HACA was developed in Matlab 7.0. All computer experiments were performed on a PC (CPU 1.86 GHz, Memory 2 GB). The parameters for the HACA are set as follows: the ant number m = 30 the vehicle capacity value Q = 150 items the maximum iteration number max ir = 200 the pheromone volatilization coefficient [rho] = 0.9 the relative influence of the pheromone trails [alpha] = 1 the relative influence of the visibility [beta] = 2 and the pheromone quantity [theta] =15.

Because the standard test instances for VRPFD are unavailable, the two-dimensional coordinates of the nodes and depot are generated randomly in [100 X 100] in this paper. The fuzzy demands of the nodes were also determined arbitrarily.

5.1. The Running Time of the HACA. In this experiment, the number of the test nodes is within the interval of 100-500 with a step of 100. Each instance runs 20 times. The average running time of each instance is used to be the solution. This is not real time problem and hence CPU times of HACA are acceptable. The results of running times are shown in Table 1.

To facilitate the comparison, HACA is also simulated in several benchmark datasets. The source of the datasets is http:// www.coin-or.org/SYMPHONY/branchandcut/VRP/data/#V. These datasets are modified to the VRPFD datasets by generating fuzzy demand. The fuzzy demand [D.sub.i] = ([d.sub.i1], [d.sub.i2], [d.sub.i3]) is randomly generated for each dataset, where the original dataset is used as [d.sub.i2] for each node. In this simulation, solution obtained by HACA is compared with HPSOGA designed by Kuo et al. [13]. Each instance runs 20 times. The average running time of each instance is shown in Table 2. The results in Table 2 prove that HACA has promising performance in solving VRPFD. HACA outperforms HPSOGA for all dataset.

5.2. The Efficiency of the TVPLCS. To determine efficiency of the TVPLCS we have developed an approach to estimate the "waste capacity," "additional distance," and "additional unloading times." The steps of the proposed calculation approach are described as follows.

Step 1. The method for processing fuzzy number into deterministic number proposed by the CA [31] is employed to estimate the "actual" demands [d.sup.a.sub.i] of each node.

Step 2. For each route planned by the HACA, the vehicle moves along the route, accumulating the sum [Q.sup.a] of the "actual" demands of all nodes that is, [Q.sup.a] = [[summation].sub.i[member of]route][d.sup.a.sub.i].

Step 3. If [Q.sub.a] [less than or equal to] Q, the vehicle can finish the task of this route, then the "waste capacity" is Q - [Q.sub.a] if [Q.sub.a] > Q, the vehicle cannot finish the task of this route. The vehicle must return to the depot, unload what it has picked up thus far, return to the node where it had a "service failure," and continue to serve the remaining nodes. Now, we can calculate the "additional distance" and "additional unloading times" due to the "service failure." The "additional distance" is equal to length of second tour of the vehicle caused because of service failure in the first tour. The "additional unloading times" are the "service failure" times. The "total distance" is the sum of the "total planned distance" and "total additional distance."

5.2.1. Test of the Travel Distance. For simplicity and perceptual intuition, we only test 100 nodes. To show the efficiency of the proposed approaches, we compare our TVPLCS based on the HACA (TVPLCSHACA) with the hybrid particle swarm optimization with genetic algorithm (HPSOGA) proposed by Kuo et al. [13]. HPSOGA employs vehicle uncoordinated strategy, and it is designed for VRPFD. This is to say, coordinating strategies/rules defined in Section 4 all were used in the experiment. At first, the coordination rule 1 is used. Then the coordination rule 2 is used. Also, the coordination rule 3 and coordination rule 4 are used if the task is not finished, the coordination rule 5 must be used else, the coordination rule 5 may not be used.

All test are calculated according to the decision maker's confidence P*, where P* varies within the interval of 0-1 with a step of 0.1. The average computational results of 10 times are calculated.

The "total planned distance" (TPD), "total additional distance" (TAD), and "total distance" (TD) are calculated. The results of TVPLCSHACA and HPSOGA are listed in Table 3.

From the results in Table 3, we can see the following: (1) with regard to TPD the result gained from the HACA is smaller than the result obtained by the HPSOGA. When [P.sup.*] = 0.9, the former is 9.35% less than the latter. Even more, the former is 10.33% less than the latter while [P.sup.*] = 1. (2) As mentioned above, TAD is due to the "service failures." The TAD result gained from the TVPLCSHACA is also smaller than the result obtained by the HPSOGA. Especially, when 0.4 [less than or equal to] [P.sup.*] [less than or equal to] 0.6, the former is close to almost half of the latter. This is to say, the TVPLCSHACA is useful for VRPFD, and TVPLCS can effectively reduce the TAD. When P* [greater than or equal to] 0.7, TAD gained from the HACA is 0, which means that there is no "service failure" in each route. However, TAD gained from the HPSOGA is 0 while [P.sup.*] [greater than or equal to] 0.9. That is, our approach is better than HPSOGA. (3) The TD of TVPLCSHACA is also smaller than the result obtained by the HPSOGA. The results can show the effectiveness of our proposed approaches.

5.2.2. Test of the Total Vehicle Number, Waste Capacity, and Additional Unloading Times. Also, we test the same 100 nodes which tested above. To show the efficiency of the proposed TVPLCS, we compare our TVPLCSHACA with the HDEA proposed by Erbao and Mingyong [12]. The algorithm employs vehicle uncoordinated strategy, and it is designed for VRPFD. All test are calculated according to the decision maker's confidence [P.sup.*], where [P.sup.*] varies within the interval of 0-1 with a step of 0.1. The average computational results of 10 times are calculated. The "plan vehicle number" (PVN), "total vehicle number" (TVN), "total waste capacity" (TWC), and "total additional unloading times" (TAUT) are tested. The results of our TVPLCSHACA and the results of HDEA (HDEA employs vehicle uncoordinated strategy) are listed in Table 4. In Table 4, capacity unit is item.

The results in Table 4 indicate the following: (1) For PVN, the value gained by HACA is close to the result planed by HDEA, and the former is better than the latter. (2) With regard to TAUT, the value gained by TVPLCSHACA is much better than the result calculated by HDEA. When P* [less than or equal to] 0.3, the number of the former is 30% less than that of the latter. When 0.4 [less than or equal to] P* [less than or equal to] 0.6, the number of the former is 50% less than that of the latter. When P* [greater than or equal to] 0.7, TAUT gained by TVPLCSHACA is 0. However, TAUT gained by HDEA is 0 till [P.sup.*] [greater than or equal to] 0.9. So, TVPLCS can effectively cut down "additional unloading times" in VRPFD, especially when the value of decision maker's preference is relatively smaller. (3) About TWC, when [P.sup.*] [less than or equal to] 0.4, all numerical values gained by TVPLCSHACA are 0, but the results of HDEA are close to 200. In other words, when a vehicle has surplus capacity, the vehicle should serve the "failure nodes" of the other failure route according to the specified TVPLCS rules. TVPLCS could be usefully employed in reduction of the "waste capacity" in VRPFD, especially when the value of decision maker's preference is relatively smaller. (4) As for TVN, the value gained by TVPLCSHACA based on the HACA is less than the result planed by HDEA. When P* [less than or equal to] 0.8, the former is nearly 25% less than the latter. Thus, the TVPLCS is very useful for the VRPFD, especially when P* is given a relatively smaller value. That is, the decision maker has an insatiable appetite for risk and wants to serve more nodes with each vehicle.

5.3. Determining the Reasonable Value of the Decision Maker's Preference. Now, we determine the reasonable value of the decision maker's preference based on the results listed in Tables 3 and 4. The TD in Table 3 and the TVN in Table 4 are selected to calculate the total logistics cost (TLC) for VRPFD. In this paper, it is assumed that the freight of TD is 5 yuan RMB per unit distance, and the fixed charge of TVN is 500 yuan RMB per vehicle. TLC is the sum of TD and TVN. The results of TLC are listed in Table 5.

From the results in Table 5 we can see the following: (1) When decision maker's preference P* [greater than or equal to] 0.6, the decision maker is risk averse and aims to minimize service failures. The optimal value of [P.sup.*] should be 0.6 or 0.7 according to TD. The best value of [P.sup.*] should be 0.7 according to TLC and TVN. However, it is not easy for us to obtain a highly credible decision maker's preference due to the variability of customer demands in practice, especially when the operations of a distributing system are only starting up. (2) While P* [less than or equal to] 0.5, the decision maker is risk preference and wants to serve more nodes with each vehicle. All values of TD, TVN, and TLC tell us that the best value of P* is 0.5. (3) The reasonable value of the decision maker's preference deduced from TVPLCSHACA is exactly the same as that inferred from HDEA.

This paper contributes to the research on the VRPFD in the following respects: (1) The fuzzy reasoning constrained program model and HACA are designed to optimize the vehicle routes, and the most appropriate values for the decision maker's confidence level [P.sup.*] were obtained by simulation. That is, if decision maker is risk averse and aims to ensure service, the best value of [P.sup.*] should be 0.7. If the decision maker has an insatiable appetite for risk and wants to serve more nodes with each vehicle, the best value of [P.sup.*] should be 0.5. (2) In particular, the TVPLCS is presented to reduce the "additional distance," "unloading times," and the "waste capacity" caused by "service failure." Numerical examples are presented to demonstrate the effectiveness of our proposed approaches. Particularly, the TVPLCS is very useful for the VRPFD when the decision maker has an insatiable appetite for risk, especially when the operations of a distributing system are only starting up and the customers' demands are difficult to estimate.

For the future research, we may consider other nondeterministic side constraints in VRPFD, such as stochastic vehicle travel time, important customer with emergent service, and time window constraint that should be considered in order to fit the practical applications.

The authors declare that they have no competing interests.

This research has been partially supported by grants from the National Natural Science Foundation of China (no. 71373216, no. 71471149 and no. 71222108), Major Project of the National Social Science Foundation of China (no. 15ZDB153), grants from the National Philosophy and Social Science Foundation of China (no. 15AJL006), Excellent Youth Project of Hunan Provincial Education Department of China (no. 15B131), and Key R&D program of Hunan Provincial Science and Technology Department of China (no. 2015ZK3049).

[1] G. B. Dantzig and J. H. Ramser, "The truck dispatching problem," Management Science, vol. 6, no. 1, pp. 80-91, 1959.

[2] G. Clarke and J. W. Wright, "Scheduling of vehicles from a central depot to a number of delivery points," Operations Research, vol. 12, no. 4, pp. 568-581, 1964.

[3] M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations Research, vol. 35, no. 2, pp. 254-265, 1987.

[4] G. Laporte, "The vehicle routing problem: an overview of exact and approximate algorithms," European Journal of Operational Research, vol. 59, no. 3, pp. 345-358, 1992.

[5] M. A. Figliozzi, "Planning approximations to the average length of vehicle routing problems with time window constraints," Transportation Research Part B: Methodological, vol. 43, no. 4, pp. 438-447, 2009.

[6] R. Sprenger and L. Monch, "A methodology to solve large-scale cooperative transportation planning problems," European Journal of Operational Research, vol. 223, no. 3, pp. 626-636, 2012.

[7] V. Pillac, M. Gendreau, C. Gueret, and A. L. Medaglia, "A review of dynamic vehicle routing problems," European Journal of Operational Research, vol. 225, no. 1, pp. 1-11, 2013.

[8] G. Kou, D. Ergu, and J. Shang, "Enhancing data consistency in decision matrix: adapting Hadamard model to mitigate judgment contradiction," European Journal of Operational Research, vol. 236, no. 1, pp. 261-271, 2014.

[9] G. Kou, Y. Lu, Y. Peng, and Y. Shi, "Evaluation of classification algorithms using MCDM and rank correlation," International Journal of Information Technology & Decision Making, vol. 11, no. 1, pp. 197-225, 2012.

[10] E. Cao and M. Lai, "The open vehicle routing problem with fuzzy demands," Expert Systems with Applications, vol. 37, no. 3, pp. 2405-2411, 2010.

[11] D. J. Bertsimas, "A vehicle routing problem with stochastic demand," Operations Research, vol. 40, no. 3, pp. 574-585, 1992.

[12] C. Erbao and L. Mingyong, "A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands," Journal of Computational and Applied Mathematics, vol. 231, no. 1, pp. 302-310, 2009.

[13] R. J. Kuo, F. E. Zulvia, and K. Suryadi, "Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand--a case study on garbage collection system," Applied Mathematics and Computation, vol. 219, no. 5, pp. 2574-2588, 2012.

[14] G. Kou and C. Lin, "A cosine maximization method for the priority vector derivation in AHP," European Journal of Operational Research, vol. 235, no. 1, pp. 225-232, 2014.

[15] G. Kou, Y. Peng, and G. Wang, "Evaluation of clustering algorithms for financial risk analysis using MCDM methods," Information Sciences, vol. 275, pp. 1-12, 2014.

[16] M. Allahviranloo, J. Y. J. Chow, and W. W. Recker, "Selective vehicle routing problems under uncertainty without recourse," Transportation Research Part E: Logistics and Transportation Review, vol. 62, pp. 68-88, 2014.

[17] Z.-H. Hu, J.-B. Sheu, L. Zhao, and C.-C. Lu, "A dynamic closed-loop vehicle routing problem with uncertainty and incompatible goods," Transportation Research Part C: Emerging Technologies, vol. 55, pp. 273-297, 2015.

[18] X. Liu, G. G. He, and W. W. Gao, "Modeling and algorithm for the multiple vehicles coordinated stochastic vehicle routing with time-constrain," System Engineering, vol. 23, pp. 105-109, 2005 (Chinese).

[19] C. K. Y. Lin, "A cooperative strategy for a vehicle routing problem with pickup and delivery time windows," Computers and Industrial Engineering, vol. 55, no. 4, pp. 766-782, 2008.

[20] J. S. Shang and C. K. Cuff, "Multicriteria pickup and delivery problem with transfer opportunity," Computers & Industrial Engineering, vol. 30, no. 4, pp. 631-645, 1996.

[21] J. Yang, P. Jaillet, and H. Mahmassani, "Real-time multivehicle truckload pickup and delivery problems," Transportation Science, vol. 38, no. 2, pp. 135-148, 2004.

[22] X. P. Hu, L. J. Sun, and L. L. Liu, "A PAM approach to handling disruptions in real-time vehicle routing problems," Decision Support Systems, vol. 54, no. 3, pp. 1380-1393, 2013.

[23] B. Liu, "Uncertain theory: an introduce to its axiomatic foundations," in Fuzzy Variables, Fuzzy Sets and Systems, S. Nahmias, Ed., vol. 1, pp. 97-110, Springer, Berlin, Germany, 2004.

[24] A. Clolrni, M. Dorigo, and V. Maniezzo, "Distributed optimization by ant colonies," in Proceedings of the European Conference on Artificial Life (ECAL '91), pp. 134-142, Paris, France, 1991.

[25] B. Bulleneimer, R. F. Hartl, and C. Strauss, "Strauss, applying the ant system to the vehicle routing problem," in Proceedings of the 2nd International Conference on Metaheuristics, pp. 1-12, 1997.

[26] K. Doerner, M. Gronalt, R. F. Hartl, M. Reimann, C. Strauss, and M. Stummer, "Savings ants for the vehicle routing problem," in Application of Evolutionary Computing, pp. 11-20, Springer, Berlin, Germany, 2002.

[27] I. Ellabib, P. Calamai, and O. Basir, "Exchange strategies for multiple Ant Colony System," Information Sciences, vol. 177, no. 5, pp. 1248-1264, 2007.

[28] Y. Gajpal and P. L. Abad, "Multi-ant colony system (MACS) for a vehicle routing problem with backhauls," European Journal of Operational Research, vol. 196, no. 1, pp. 102-117, 2009.

[29] B. Yu, Z. Z. Yang, and B. Z. Yao, "A hybrid algorithm for vehicle routing problem with time windows," Expert Systems with Applications, vol. 38, no. 1, pp. 435-441, 2011.

[30] C. L. Fleming, S. E. Griffis, and J. E. Bell, "The effects of triangle inequality on the vehicle routing problem," European Journal of Operational Research, vol. 224, no. 1, pp. 1-7, 2013.

[31] C.-C. Chou, "The canonical representation of multiplication operation on triangular fuzzy numbers," Computers & Mathematics with Applications, vol. 45, no. 10-11, pp. 1601-1610, 2003.

Chang-shi Liu, (1,2,3,4) Gang Kou, (5) and Fu-hua Huang (1)

(1) School of Management, Hunan University of Commerce, Changsha 410205, China

(2) Mobile E-Business Collaborative Innovation Center of Hunan Province, Hunan University of Commerce, Changsha 410205, China

(3) Key Laboratory of Hunan Province for Mobile Business Intelligence, Hunan University of Commerce, Changsha 410205, China

(4) Institute of Big Data and Internet Innovation, Hunan University of Commerce, Changsha 410205, China

(5) School of Business Administration, Southwestern University of Finance and Economics, Chengdu 611130, China


RELATED ARTICLES

Although this might be going in the opposite direction of the final destination, it reduces the chances of an accident and cuts delays caused by waiting for a gap in the traffic, which would also waste fuel.

UPS have designed their vehicle routing software to eliminate as many left-hand turns as possible (in countries with right-hand traffic).

Typically, only 10% of the turns are left turns.

TIPS FOR SAVING ON CAR FUEL

  • Accelerate gradually.
  • Anticipate your stops - when approaching a red light, let your foot off the gas as soon as possible.
  • In the summer, drive during cooler parts of the day, as cooler, denser air can boost power and mileage.
  • Avoid long warm ups in the morning as they waste fuel.
  • Use air conditioning - it creates less drag on the engine than driving with the windows open.
  • Maintain recommended tire pressure.
  • Keep the air filter clean - clogged filters can result in fuel wastage.
  • Drive at the speed limit.

As a result, the company claims it uses 10million gallons less fuel, emits 20,000 tonnes less carbon dioxide and delivers 350,000 more packages every year.

The efficiency of planning routes with its navigation software this way has even helped the firm cut the number of trucks it uses by 1,100, bringing down the company’s total distance travelled by 28.5m miles – despite the longer routes.

It seems incredible that not turning left can lead to such significant savings.

The TV series Mythbusters tested this idea and confirmed that, despite many more turns, the policy of only turning right does save fuel.

In their one truck experiment they travelled further, but when you scale this up to a global level, UPS really does travel fewer miles in total.

The success of UPS’s policy raises the question, why don’t we all avoid turning left (or right, depending on what country we’re in), as we drive around cities on our daily commutes?

If everyone did it, the carbon savings would be huge and there’d probably be far less congestion.

The problem is that not every journey would be made more efficient by following this strategy, and most people are likely only to change their driving style if they personally benefit.

As with anything related to reducing climate change, if everybody else did it then things would get better and you wouldn’t have to change your lifestyle at all to benefit.

As a result of their no left turn policy, the company claims it uses 10m gallons less fuel, emits 20,000 tonnes less carbon dioxide and delivers 350,000 more packages every year

But it only needs a few people to not cooperate and the whole system breaks down.

This is a good example of the prisoner’s dilemma, the famous game theory problem.

If everybody cooperated then the system as a whole would be much better, but the best thing for an individual when everyone else is cooperating is to be uncooperative and reap the rewards of everybody else’s sacrifices.

So, if you cannot persuade people to always turn right (or left) for the benefit of everyone, it might be down to governments to encourage or even enforce the strategy.

For example, we could plan roads that make it more difficult to turn through the traffic.

It would take a brave city planner to implement this, but if UPS can save 10million gallons of fuel, how much could a whole city or even a whole country save?


Minimizing the Carbon Footprint for the Time-Dependent Heterogeneous-Fleet Vehicle Routing Problem with Alternative Paths

where is the energy (J) required by the vehicle type u going from customer node i to node j in time zone m on route n Wu is the empty weight of vehicle type u (kg) is the load (kg) of vehicle type u on route n after passing through node i is the vehicle speed (m/s) in time zone m on path z between nodes i and j is the distance (m) traveled by the vehicle on route n in time zone m on path z between customer nodes i and j . Furthermore, because the surface area of each vehicle type is different, Equation (3) is modified to:

3.1.3. Mathematical Model

The objective of our problem is to minimize the amount of the energy used based on the improved equation combined with variables , which is given as follows:

Note that is one or zero according to the condition whether vehicle type u has passed through path z between nodes i and j on route n . If the condition is true, then = 1 otherwise, = 0. Because the result unit obtained by the original objective equation is in J· m 2 / s 2 , our requirement is that this unit must be converted to a kilowatt-hour. One liter of gasoline can produce approximately 8.8 kilowatt-hours of energy [9] and approximately 2.32 kg of CO2 [9]. Thus, this objective equation is multiplied with a coefficient of 2.32/8.8/360000. The following constraint ensures that each node is only passed once, where represents whether vehicle type u passes node i on route n . If so, then = 1 otherwise, = 0.

The following constraint ensures that only equals 0 or 1.

The following constraint ensures that only equals 0 or 1. If vehicle u passes through path z between nodes i and j on route n , then equals 1 otherwise, equals 0.

The following equation calculates the routing time in each situation.

The following equation calculates the time point that the vehicle reaches customer node j on route n , where represents the time that the vehicle left node i .

The following equation calculates the total routing time from node i to j on route n .

The following equation calculates the routing distance on route n in time zone m on path z between nodes i and j , where Zi,j is the path selected between i and j .

Cost_Matrix Distance: Vehicle routing problem! - Geographic Information Systems

Vehicle routing involves travel distances and the corresponding travel times. The add-in stores the locations of selected points within a region on the Distance worksheet. These are the map locations. Points may be specified with either Cartesian or Geographic coordinate systems. Distances between map locations are specified in miles or kilometers. Distances are computed with either the straight-line measure (Euclidian) or by the length of the line that follows the curvature of the earth (the Great Circle Distance). Options regarding locations on the map are determined by filling the dialog below. A button on the Start worksheet calls this dialog. The example is the 446 point representation of the Austin area as pictured on the summary page.

The Name and Map Points fields are filled with the name of the distance worksheet and the number of map locations. The add-in creates a second worksheet, the Customer worksheet, to store customer locations. The number of locations is entered in the Customer Points field. Both distance and customer worksheets use four columns to represent the index, name and the two coordinates for each point. The Extra Columns field adds blank columns to hold additional data such as address or phone number. The Same Map and Customer button makes the number of customer points equal to the number of map points and links the customer data to the map data with formulas. This is illustrated on the summary page.

The three decision pairs in the center of the dialog set the type of coordinates, distance measure and distance calculation. With Cartesian Coordinates the Euclidean measure is always used. It is the straight line distance between two points. The Great Circle measure computes the distance between two points considering the curvature of the earth. The equations assume the earth is spherical. This measure is always used when Geometric Coordinates specify the locations.

When the Provide Matrix for Distances button is checked, the point-to-point distances between all pairs of map locations are calculated and stored in a square matrix on the distance worksheet. Otherwise only the coordinates are stored and the distances are computed as needed. Of course, when a large number of map locations is specified, the matrix defining the distances is correspondingly large. Although the matrix is initially filled with distances computed with one the measures, the purpose of the matrix is to hold more accurate distance values.

The concept used for this analysis tool is that most travel is between major travel destinations in a local region. Map locations identify major intersections, apartment complexes, shopping malls and business parks. Over time the distances or travel times between these fixed locations can be measured carefully or obtained from some database of travel times such as Google Maps or GPS systems. Individual customer locations can be located relative to these fixed locations and the extra travel time estimated using the Euclidean measure and average travel speeds.

The Random Coordinates checkbox causes the add-in to generate random coordinates for the locations. This is handy when learning about the add-in and building large models without much data. The random number seed controls the sequence of random numbers. Change the seed to obtain a different set of map points. The base values determine the origin of the distance map and the range determines the upper and lower bounds of randomly generated map points.

On clicking the OK button on the dialog, the distance worksheet created by the add-in is illustrated below. The names are in column E and geographic location coordinates are in columns F and G. Column H is an extra column intended for some additional data item regarding map points. Although it is customary to specify geographic coordinates in degrees, minutes and seconds together with N, S, E, and W, designations, we use the more concise decimal coordinates (latitude, longitude). The origin for latitude is the earth's equator and measures distances north and south of the equator. Latitude varies from -90, the latitude of the south pole to +90, the latitude of the north pole. Points south of the equator have negative latitude and points north of the equator. have positive latitude. The origin of longitude is the Royal Observatory, Greenwich England, with points east of Greenwich having negative values and points east having positive longitude. Longitude varies from -180 to +180. The international date line is at both maximum and minimum longitude.

The numbers in column K are used to measure the distance of each map location from a fixed location on the map. To illustrate, K6 and K7 hold the coordinates of the first customer location. Numbers starting in row 15 and continuing compute the distance to all 446 map points. K8 computes the minimum value in this list and K9 is the map location closest to the first customer. K10 holds the map location name. This list is used to assign customers to their closest map points.


Electric Vehicle Routing Problems with Stochastic Demands and Dynamic Remedial Measures

With the rapid development of e-commerce, logistic enterprises must better predict customer demand to improve distribution efficiency, so as to deliver goods in advance, which makes logistics stochastic and dynamic. In order to deal with this challenge and respond to the concept of “green logistics,” an electric vehicle routing problem with stochastic demands (EVRPSD) and proactive remedial measures is investigated, and an EVRPSD model with probability constraints is established. At the same time, a hybrid heuristic algorithm, combining a saving method and an improved Tabu search algorithm, is proposed to solve the model. Moreover, two insertion strategies with the greedy algorithm for charging stations and dynamic nodes are introduced. Finally, a large number of experimental data show that the heuristic algorithm proposed in this paper is feasible and effective.

1. Introduction

With the rapid development of e-commerce, the order quantity of logistic enterprises has increased rapidly, and the customers have higher requirements on the timeliness of delivery than before. The traditional collaborative pattern for processing orders (consumers, e-commerce platforms, sellers, and logistic enterprises) has been difficult to meet the requirements under a large number of orders, and it is urgent to transform the current pattern of logistics.

A huge number of orders means that a lot of demand-related data can be obtained therefore, e-commerce platforms have the ability of predicting consumer demand before the big promotion, and then logistic enterprises can transport the goods to the area near the target customers in advance. Once customers submit their order, the corresponding goods will be delivered from the nearest warehouse immediately, and it can greatly shorten the delivery time, realizing the immediate delivery. At present, some logistic enterprises have started to implement this pattern by establishing “front warehouses” that are near to the end customers, whose service radius is 3–5 kilometers, so it can shorten the delivery time from days to hours or even minutes.

Front warehouses are characterized by the stochastic demand, which can be predicted by historical data, while the real demand is confirmed until a delivery vehicle arrives at a front warehouse. Therefore, the probability of insufficient goods may occur, and the vehicle may return to the depot for replenishment during the distribution process. To investigate this scenario, scholars proposed the capacitated vehicle routing problem with stochastic demands (CVRPSD) [1]. In addition, when the vehicle starts from a regional warehouse to a front warehouse, there may be a replenishment request from new front warehouses, whose position and demand cannot be predicted in advance, and such a demand is defined as dynamic. The distribution center constantly updates the routing plan according to the emerging dynamic demand, which is defined as the dynamic demand vehicle routing problem (DVRP) [2]. Ecological logistics is another issue we need to consider toward the current serious environmental problems. At present, the general solution is to use electric vehicles instead of traditional fuel vehicles in the logistic industry. However, due to the limited battery capacity, electric vehicles often need to be charged or change battery on the way one or more times to successfully complete the whole task, which will increase the total cost to some extent. Therefore, it is necessary to develop a reasonable charging/changing strategy to reduce the distribution cost, and a new problem, electric vehicle routing problem (EVRP), is emerged [3].

In order to meet the needs of real delivery scenarios, we will consider both the randomness and dynamics of customers and the mileage constraints of vehicles, thus proposing a new variant, namely, electric vehicle routing problems with stochastic demands and dynamic remedial measures. However, it should be noted that we have not considered the customer’s time window and the scenario of multiple distribution centers.

This paper is organized as follows. In Section 2, we will extend from the above three directions. In Section 3, we briefly describe the electric vehicle problem and give some general assumptions. In Section 4, we introduce an EVRPSD mathematical model in detail and propose an evaluation method for battery swap station insertion as well as the strategy of dynamic customer insertion. And, the detailed implementation of the CW-TS heuristic algorithm for solving the model is described in Section 5. The computational results are reported in Section 6. Finally, Section 7 contains a summary and future works.

2. Literature Review

There are a large body of literatures focusing on CVRPSD. Stewart and Golden [1] established a mathematical model based on the opportunity constraint and binary possibility theory for CVRPSD. The opportunity constraint model stipulated that a stochastic customer should be served only with an acceptable probability of failure, regardless of the additional cost caused by service failure, while the binary possibility theory considered the opportunity cost caused by service failure. Dror et al. [4] transformed the stochastic problem into a series of determined problems through a phased approach and obtained the solution of the problem under the consideration of the number of service failures.

The methods to solve the CVRPSD model are divided into exact algorithms and heuristic algorithms. For the former, Gauvin et al. [5] designed a new branch-cut-and-price algorithm to solve CVRPSD, and a Tabu search heuristic and a bidirectional labeling algorithm were utilized to accelerate the pricing stage. Gendreau et al. [6] proposed an L-shaped algorithm for CVRPSD with uncertain customer location, which takes the location of the depot and the tour plan as decision variables. Numerical results shown that the algorithm was feasible and effective by performing on an instance containing 100 nodes. For the latter, Lei et al. [7] used the adaptive large neighborhood search algorithm to solve the routing problems of uncertain demand with time windows. Bertazzi and Secomandi [8] introduced a faster rollout search for the vehicle routing problem with stochastic demands and restocking and designed a quick rollout algorithm to solve the problem. In order to reduce the running time, they also proposed a new method to estimate the expected cost of the route when executing any VRP rollout algorithm with replenishment.

The existing literature on DDVRP mainly focuses on the dynamic problem with uncertain customer demands. Qureshi et al. [9] solved DDVRP with soft time windows by means of the column generation algorithm, updating route status by using an event update strategy dynamically. Abdallah et al. [10] constructed a DDVRP model based on the capacity constraint and proposed an improved genetic algorithm to boost the solution quality according to the optimal combination of relevant parameters of selection, crossover, and mutation operators. Kuo et al. [11] established a mathematical model aiming at maximizing the number of serviced customers and minimizing the average customer waiting time for DDVRP with uncertain service time and proposed a regular update strategy to transform the dynamic problem into a series of static problems for the routing plan. Ge et al. [12] built a mathematical model minimizing the total cost for the open DDVRP and proposed a cloud genetic algorithm with a faster convergence rate than its classic counterpart to solve the DDVRP model. At the same time, the authors also introduced the concept of the key point for updating the routes dynamically. Okulewicz and Mańdziuk [13] extended DDVRP to the dynamic demand vehicle routing problem with multidistribution centers and adopted a two-stage multiswarm particle swarm optimization (2MPSO) heuristic to solve the model. Ghannadpour et al. [14] established a multiobjective DDVRP model with capacity and fuzzy time window constraints, aiming at minimizing the number of vehicles, total driving distance, vehicle waiting time, and maximizing user satisfaction. In addition, the genetic algorithm was used to solve the model. Ge et al. [15] studied the data-driven proactive vehicle routing optimization based on the historical distribution data of logistic companies, and four models were established for predicting customer demands, customer clustering, proactive demand quotas, and replenishment strategies.

Research studies on EVRP mainly focus on vehicle load, battery capacity, and time window constraints and on the battery charging or swap strategy. Conrad and Figliozzi [16] proposed an EVRP-C to solve the “range anxiety” problem. Erdoğan and Miller-Hooks [17] also proposed an EVRP-C model, which assumes that the charging time and the service time of each customer are fixed and created feasible routes by using Clark–Wright’s saving method to insert the charging stations. Schneider et al. [18] extended the green vehicle routing problem (G-VRP) to the electric vehicle routing problems with time windows (EVRP-TW). They assumed that the vehicle visited the charging station at most once during the transportation process and established a mathematical model, in which the objective is minimizing the number of vehicles and the total travel distance. Lin et al. [19] proposed a partial charging strategy for EVRP-TW, i.e., the vehicle’s charging duration and location are the decision variables. Alejandro and Christelle [20] introduced a piecewise linearization function to fit the nonlinear charging process. Compared with the traditional linearization charging function, the new function reduced the calculation error of charging time. Based on the traditional linear discharging model, Goeke and Schneider [21] proposed a nonlinear battery energy consumption model based on real travel distance, road slope, vehicle speed, and load. Yang and Sun [22] introduced a BSS-EV-LRP model based on the location of battery swap stations. It included both the locating problems and the routing optimization under the limit of battery capacity, and they designed a hybrid approach called TS-MCWS which combines Tabu search and modified the Clarke and Wright saving algorithm to jointly solve the problem. In this problem, TS is designed to search the location strategy and a modified Clarke–Wright saving method undertakes the routing decision based on this location solution. On this basis, Hof et al. [23] designed an adaptive variable neighborhood search (AVNS) algorithm for the same problem. Numerical analysis showed that the method was robust and could obtain solutions with higher solution quality than SIGALN and TS-MCWS in most cases. Shao et al. [24] studied an electric vehicle routing problem with charging time and variable travel time. For obtaining the routes, the vehicle departure time at the depot, and the charging plan, they used the genetic algorithm, and to reflect a dynamic traffic environment, they implemented fluctuations in travel time.

To sum up, scholars have contributed a lot of research on dynamic vehicle routing and electric vehicle routing [25–27]. However, with the rapid development of the logistic industry, the realistic logistic scenarios, such as cash-in-transit service of banks, product oil distribution, beer supply, and garbage collecting, need to take into account the uncertainty and environmental friendliness during the distribution process, and the research studies mentioned above lack techniques and strategies to solve such real cases. Therefore, this paper studies the routing optimization problems of s with stochastic demands and dynamic remedial measures. The contributions of this paper are the following four-fold: (1) Formulating an EVRPSD model with the opportunity constraint (2) Establishing an effective remedy strategy to fully utilize the residual load (3) Designing a two-stage heuristic algorithm to solve the EVRPSD model (4) Enriching the display of the vehicle route and thus improving the decision maker’s experience

3. Problem Description

The problem studied in this paper can be described as follows: the customer demand is divided into stochastic demand (the location of the customer is determined, and the demand is subject to a probability distribution) and dynamic demand (the time, location, and demand of the customer can only be confirmed if and only if the customer requests have arrived), and a distribution plan consists of two cycles.

The first cycle: the predicted demand of each stochastic customer is obtained according to the historical demand data in the first stage, and the initial solution is generated according to the prediction the vehicle starts from the distribution center and visits stochastic customers in sequence according to the initial solution, while the information center will receive new requests (generated by dynamic customers) in the time window [T, T0] during the transportation process in the second stage, the actual demand of customer i (denoted qi) is attained when the vehicle k arrives at the location along with route rk, and then the remainder capacity of k is determined as to whether qi is satisfied. If not, the vehicle k returns to the distribution center after its rest of the goods are uploaded to i (consider this customer point as a “failure point”), and the remainder demand of customer i will be assigned to the next cycle. Judging the remainder capacity of k whether it satisfies the demand of the next stochastic customer i + 1, if the probability of this estimate is less than the risk preference α, the vehicle k will go to the customer i + 1 otherwise, stochastic customers after i (consider this customer point as a “remedial point”) in route rk will be assigned into the second cycle distribution. According to the vehicle’s current capacity and dynamic customer information collected by the information center, dynamic customers would be appropriately inserted to the current route rk and the vehicle will return to the distribution center after completing its tasks. In addition, if the vehicle has rest capacity too before it successfully serves the last customer j of the route, the insert operator can be repeated until its rest capacity is close to zero, and we call j as the “key point” in this condition. If there are dynamic customers that violate the capacity constraint, they will be assigned to the second cycle.

The second cycle: the stochastic customers and dynamic customers unserved in the first cycle will be served. The objective is to minimize the total cost of two-cycle delivery (distance cost and fixed cost of vehicles). Since it is necessary to ensure that the electric vehicle has a positive power in the distribution process, the battery replacement plan will change with the adjusting route plan, which will further increase the complexity of the problem. Figure 1 describes the whole process of distribution, in which stochastic customers 2, 4, and 5 and dynamic customer 3 are included in the second cycle.


Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach ☆

The time-dependent vehicle routing problem with time windows (TDVRPTW) is examined in this study. A mathematical model for the TDVRPTW is formulated by considering the time-dependent vehicle speeds, capacity, travel time, wait time, customer demand, service time, time window, impact of dynamic loads, and travel speed effect on vehicle carbon emissions. The objective of the TDVRPTW model is to minimize the sum of the fixed costs of the vehicle used, as well as the costs of drivers, fuel consumption, and carbon emissions. A calculation method for the road travel time across time periods with time-dependent speeds is presented. A congestion avoidance approach is proposed to avoid peak hour traffic congestion and temporal traffic congestion. An improved ant colony algorithm with a congestion avoiding approach (IACACAA) is elucidated according to the characteristics of the TDVRPTW model. The effectiveness of the proposed approaches was demonstrated in several computational experiments. The results show that the proposed IACACAA can scientifically plan the departure time and driving route for each vehicle, effectively avoid traffic congestion, and reduce the total distribution costs. The congestion avoidance approach effectively reduces vehicle fuel consumption and carbon emissions and protects the environment.


Introduction

The early research of the Vehicle Routing Problem (VRP) can be traced back to [1], shown as an essential issue with tremendous effect to the economy and society. In the classical Vehicle Routing Problem with Time Windows (VRPTW) [2], at the beginning of a planning horizon, a fleet of identical vehicles leave a center depot to visit/service a sequence of customers with certain demands, composing a number of so-called routes. Every customer is visited exactly once, satisfying the constraints (time window) specified by the customers. The sum of customer demands on each route cannot exceed the capacity of a vehicle, and all vehicles have to return the depot before the end of the planning horizon. The most common objectives in VRPTW are minimization of the number of vehicles used and minimization of the total travel distance.

Vehicle routing problem variants

Based on the VRPTW model, a large number of classic VRP variants have been proposed with diverse side constraints from practical scenarios. In this section, only the most relevant variants to our study are reviewed. In Vehicle Routing Problem with Pickups and Deliveries (VRPPD) [3], a service demand consists of picking up shipments from a customer and the associated delivery to another customer. Especially, if the depot is the only one pickup point and all the customers are delivery destinations, or in another case, all the customers are pickup points while only the depot is the delivery location, the problem is called a One-to-Many-to-One problem. If the customers are pickup points as well as delivery points, the problem is Many-to-Many. Last but not least, it is a One-to-One problem when the pickup demand of a customer is the delivery demand of another specific customer [4].

Furthermore, if the shipments can be consolidated, the problem would be classified as Less-than Truckload Transportation otherwise, it is a Full Truckload Transportation (FTT) problem [5]. Container transportation problem is a specific variant of FTT, where one truck can carry only one demand item (container). Zhang et al. [6] model the container transportation problem with a node-based network, which is commonly used in VRPTW. The model integrates all activities of completing the transportation of a container into a so-called load node. This method has been widely used in the VRPPD with high loading and unloading time [7, 8].

In some cases of VRP, the scheduling horizon is very long, e.g. in soft drink industry, grocery distribution and waste collection. Their scheduling is usually performed over multiple periods/shifts, and the associated problems are categorized as Multi-Period Vehicle Routing Problem (MPVRP) [9]. Especially, when there is a specific service frequency to each customer over the scheduling horizon, the problem is called a Periodic Vehicle Routing Problem (PVRP) [10]. In this case, each customer may be visited more than once. The solution of PVRP is a combination of service shifts of customers, instead of the scheduled routes of one single period.

Apart from the two objectives in VRPTW mentioned above, there are various other objectives widely used in VRPs, e.g. minimizing the travel time, the waiting time, and other operational cost, maximizing the balance of workload, and so on [11]. With the increasing concern to the environment in recent years, the carbon emission and petrol consumption have also been considered in the VRP community, leading to the Pollution-Routing Problem and Green Vehicle Routing Problem [12]. From the cost perspective, labor cost (driver salary) usually is the dominated component in the overall cost [13]. This is one of the reasons why minimizing the number of vehicles used is a primary objective in VRPs, as fewer vehicles require fewer drivers being hired. In addition, making use of fewer vehicles generally implies a lower fuel consumption and a higher utilization rate of the vehicle capacity. When more than one objective are considered in a VRP, it is called a Multi-Objective Vehicle Routing Problem (MOVRP).

Existing methods

After decades of study in VRP, both exact and approximate methods have been extensively investigated. Exact methods explore the solution space of a problem exclusively to find the optimal solution. However, a critical issue of such methods is the unrealistic computational time needed searching the enormous size of the solution space in real-world problems. On the other hand, approximate methods (or heuristics) do not guarantee the optimality of solutions produced, but generate a good approximation of the optimal solution in an acceptable computation time [14]. Metaheuristics and Hyper-Heuristics methods guide the search with various strategies, showing powerful performance in solving diverse large scale and complex VRPs [15].

Population-based metaheuristics, such as Evolutionary Algorithms, Scatter Search, and Ant Colony Optimization Algorithms, evolve a population of solutions [14]. Using population improves the diversification of searches, these type of methods show powerful exploration ability while achieve high quality solutions in multi-objective and highly constrained problems. However, larger population is hard to operate and may greatly affect algorithm performance. For example, in Genetic Algorithm, which is a widely used population-based metaheuristic in VRPs, it is hard to use crossover to partition the periods and routes in the solution representation (e.g. genotype/chromosome) for MPVRP. Besides, in large size problems, the long chromosome and the associated large solution population is hard to manage as well. Population-based metaheuristics are not suitable to large scale problems with complex structures and constraints such as the MPVRP considered in this paper.

Differently, in each iteration of single solution-based metaheuristics, only one solution is updated by employing neighbourhood operators at each move during the search. In different algorithms, such as Tabu search [16], Simulated Annealing [17], and Variable Neighbourhood Search [18], different strategies are used in the Acceptance Criterion and Neighbourhood Operator Selection.

Metaheuristic algorithms are often designed to address specific problems by striking a balance between the diversity and intensity of the search for the specific problems. In the literature, a large number of problem specific and knowledge intensive metaheuristics have been developed for VRPs [19, 20]. Differently, Hyper-Heuristics is a type of high level algorithms which aim to develop generic approaches beyond the problem specific metaheuristics [21, 22]. Hyper-Heuristics work at a higher level to generate or select a set of Low-Level Heuristics (LLH) in a common framework, while the LLH execute the operations on problem solutions. Hyper-Heuristics focus on designing the high level framework, called High-Level Heuristic (HLH), instead of searching the specific solutions for the problem confronted. In a well-designed Hyper-Heuristics algorithm, its HLH would adaptively adjust the LLH used, creating proper algorithms for various searching scenarios for the given instances.

Hyper-heuristics approaches can be categorized to two classes: Heuristic Selection and Heuristic Generation [23]. Heuristic Selection methodologies choose existing heuristics from the LLH pool to tackle the problem given, while the methodologies of Heuristic Generation generate new heuristics using existing heuristics as the components. What’s more, each above class can be further divided into two subcategories, namely Construction Heuristic and Perturbation Heuristic, according to the constructive or perturbative low level heuristics used. Construction Heuristics construct solutions using the given LLH, while Perturbation Heuristics produce new solutions by perturbing existing solutions. More details can be found in [24, 25].

As a classic combinatorial optimization problem, VRP is an essential application of hyper-heuristics. Garrido and Riff [26] propose an evolutionary hyper-heuristic for Dynamic Vehicle Routing Problem (DVRP). Each genotype in this evolutionary algorithm consists of a constructive heuristic, an improvement heuristic and an ordering heuristic. This generative construction hyper-heuristic adapts well to the dynamic scenario in DVRP. Both hyper-heuristics of [27] and [28] obtain competitive results in Capacitated Vehicle Routing Problem (CVRP). The former generates LLH by searching the space of heuristic component (i.e. neighbourhood structure, neighbourhood combination, local search configuration and acceptance criterion), while the latter adjusts the order of LLH to perturb the current solution, incorporating an adaptive ordering scheme in an Iterated Local Search framework. In [29], besides the selection of LLH, a Gene Expression Programming framework is also proposed to automatically generate the acceptance criterion for different problem instances. The proposed method shows promising results in DVRP and CVRP.

Vidal et al. [30] propose an unified hybrid genetic search framework (UHGS), which replaces the mutation with a unified local search (ULS). In ULS, the route-evaluation operators vary according to the change of problem attributes, aiming to provide a general-purpose solver for diverse VRP variants. UHGS produces results better than or close to the state-of-the-art results on benchmarks. However, the experiment results show that its computation time increases significantly in MPVRPs again due to the period and route partition problem as explained above on genetic algorithms. The long computation time impedes its application to large scale MPVRP.

Benefiting from decades of intensive research in VRP, a large number of excellent heuristics have been developed, providing sufficient LLH for designing high performance hyper-heuristics. Potvin and Rousseau [31] and Taillard et al. [32] propose the 2-opt* and CROSS-exchange heuristics, respectively, which show excellent performance in routing problems with time windows. However, when facing large-scale problems with complex structure, they often converge prematurely due to their relatively small change (low perturbation) to a solution in each iteration, thus the search is often stuck to local optimum.

Shaw [33, 34] proposes the Large Neighbourhood Search (LNS) heuristic which removes a number of nodes (e.g. demands/customers) from the current solution and then reinserts them to generate an updated new solution (Destroy & Repair). This heuristic brings greater changes (higher perturbation) to escape from local optimum and avoid premature convergence. It obtains the best results in several VRP variants, although a larger computation time is required in each iteration [35]. A similar strategy called Ruin & Recreate is proposed in [36].

Nagata and Bräysy [37] propose the Guided Ejection Search (GES) heuristic combining the ideas of LNS and Ejection Pool methods [38]. In each iteration of GES, one route is removed and then the nodes of the removed route are reinserted into the destroyed solution. Any infeasible partial solutions are accepted with penalties. GES outperforms the existing heuristics on minimizing the number of routes, but longer computation time for each iteration is needed. For more details, see [39, 40].

Much research on MOVRP have been done as well. In some of them, a set of non-dominated solutions based on Pareto Dominance [41] are generated, providing the decision maker a pool of candidate solutions as a reference (Pareto Methods). In the literature, the Pareto Methods are mainly used in Evolutionary Algorithms [42,43,44,45]. Differently, in the other research, one single optimal solution is pursued. In this case, either the problem objectives are projected into one single objective and the problem is solved as a single-objective problem (Scalar Techniques), or different priorities are assigned to objectives which are considered separately (Non-Scalar and Non-Pareto Algorithms). More methodologies for MOVRP can be found in [46].

In real-life, the vehicle scheduling of different types of shifts are usually considered separately as independent problems. In this paper, a real-world Mixed-Shift Vehicle Routing Problem with Time windows (MS-VRPTW) is studied. A construction heuristic and a selection perturbation hyper-heuristic, which combine the scheduling work of two types of shifts, are proposed for the MS-VRPTW. The proposed algorithms integrate the independent resource for the two types of shifts, aiming to increase the utility of vehicles and reduce the scheduling stress for logistic companies. The algorithms are tested on a set of benchmark instances with different features.

The rest of this paper is organized as follows: Section 2 introduces the problem background and presents the mathematical problem model. Section 3 introduces the proposed solution methods. The benchmark instances and computation experiments are presented in Section 4. Section 5 shows the conclusions of this paper.


This PDF file Vehicle Routing Problem with Backhaul, Multiple Trips and Time Window | Ong | Jurnal Teknik Industri 2 PB

Abstract: Transportation planning is one of the important components to increase efficiency and effectiveness in the supply chain system. Good planning will give a saving in total cost of the supply chain. This paper develops the new VRP variants’, VRP with backhauls, multiple trips, and time window (VRPBMTTW) along with its problem solving techniques using Ant Colony Optimization (ACO) and Sequential Insertion as initial solution algorithm. ACO is modified by adding the decoding process in order to determine the number of vehicles, total duration time, and range of duration time regardless of checking capacity constraint and time window. This algorithm is tested by using set of random data and verified as well as analyzed its parameter changing. The computational results for hypothetical data with 50% backhaul and mix time windows are reported.

Keywords: Vehicle routing problem, vehicle routing problem with backhauls, multiple trips, time window, sequential insertion, ant colony optimization, ant system.

The Transportation cost is one of component cost in logistic system which has dominated total cost wholly. This transportation cost must be efficient in order to give contribution for decreasing total cost and increasing the firm’s competitive advantage. Finding efficient vehicle routes and its schedule are a representative logistics problem. Vehicle routing pro-blem (VRP) goals to find a set of tour for several vehicles from a depot to a lot of customers and return to the depot without exceeding the capacity

con-straints of each vehicle at minimum cost (Bin et al.

[1]). Brandao [2] defines more specific that is distri-buting products to number of customers in certain region with deterministic demand.

Various types of VRP model have been developed to accommodate various real situations. Suprayogi [14] explained it such as VRP with time windows (VRP-TW), VRP with multiple trips (VRPMT), and VRP with simultaneous pick-up delivery (VRPPD). There is a specific variant that discusses the separating service between linehauls customer and backhaul customer, VRP with backhauls (VRPB). Generally, VRPB can be classified as two types of problem those are VRPB with customer priority and VRPB

without customer priority (Tavakkoli-Moghaddam et

1 Faculty of Industrial Teknology, Industrial Engineering

Department, Institut Teknologi Harapan Bangsa. Jl. Dipatiukur 80-84, Bandung 40132. Email: [email protected]

2 Faculty of Industrial Technology, Industrial Engineering

Department, Bandung Institute of Technology, Jl. Ganesha 10, Bandung 40132. Email: [email protected]

Received 19 January 2011 revised1 28 February 2011 revised2 15 March 2011 Accepted for publication 30 March 2011.

Crispim et al. [6] explained that VRPB has same

constraint with VRP but there is an addition constraint, linehauls customers are served before backhaul customers. VRPB model must be adjusted with real condition that considers multiple trips and time window, VRPBMTTW. The example problem for this variant is finding the vehicle routes for chemical distributors. Distributors have to deliver chemical substances to a lot of agents and retailers which spread at certain area. Distributors also have to pick up the chemical substances from suppliers. The separation between linehauls and backhaul is caused by hazardous chemical substances that cannot be put together at the same vehicle.

A number of vehicles are assigned to deliver chemical substances and after that, the vehicles are assigned to pick up chemical substances. This service can be done in the time window and certain planning horizon, as well as vehicles are allowed to go back and forth to distributor for loading and unloading chemical substances.

Various techniques have been developed to solve

VRP. Bin et al. [1] said that VRP is a hard

combina-torial problem. Consequently, VRP is generally solved by using heuristic and meta-heuristic approach, such as 2 opt, 3 opt, simulated annealing, genetic algorithm, tabu search, ant colony optimiza-tion, etc.

Now, metaheuristic approach is mainly used because of its ability to solve the problem more intensively. Ant colony optimization (ACO) is one of the metaheuristic approaches that can be used to solve hard combinatorial problems. Dorigo and Blum [10] concluded that ACO gives a good solution in short

vehicle routing problems, sequential ordering problems, resource constraint problems, and open shop scheduling problems. Mong Sim and Hong Sun [12] also said that ACO results good solution for routing and balancing problem. In his research, Bell and McMullen [3] explained that ACO results good solution for VRP. ACO gives good solution and efficient enough for very complex problem (Doerner

There are two general ways to generate VRP initial solution, those are using savings criterion and inserting customer sequentially to the route with cost criteria (Laporte et al. [11]). Sequential inser-tion is often used to solve vehicle routing problem because it is easy to be modified to accommodate complex constraints.

VRP with Backhaul and Time Window (VRPB-TW)

VRPB-TW model is a model developed from the basic model VRPB by adding constraint of time window on each customer. Cho and Wang [5] developed a model VRPB-TW that minimize the amount of vehicles and routing time by starting from the depot and ends at the depot. The VRPB-TW consists of finding a set of vehicle routes with a lot of constrains, such that: (1) each vehicle services one

route (2) each customer node i is visited exactly

once (3) the quantity of goods on-board never exceeds the vehicle capacity (4) the linehauls customers precede the backhauls on each vehicle route (5) the start time on each vehicle route is greater than or equal to the time window’s lower bound at depot (6) the return time on each vehicle route is less than or equal to the time window’s upper bound at depot (7) the time of beginning of service at each node i is less than or equal to the time

window’s upper bound li and (8) the time of

beginning of service at each vertex i is greater than

or equal to the time window’s lower bound ei. Cho

and Wang [5] solve this model with metaheurisic technique threshold accepting (TA). Unlike Zhong and Cole [16] complete with local search techni-ques for similar problems.

VRP with Multiple Trips, Time Window, and Pickup Delivery (VRP-MTTWPD)

VRPMTTWPD is a combination of variants vehicle routing problem with multiple trips (VRPMT), vehicle routing problem with time window

(VRP-TW), and vehicle routing problem with pickup

delivery (VRPPD). The characteristics of VRPMTT-WPD model is that each customer has a

time-win-dow, each vehicle can have more than one route

during the planning horizon, and the customer

receives the supply of goods from the depot and send the goods to the depot. These models will get a set of tours that meet the delivery demand and also pickup demand (Suprayogi and Priyandari [13]).

There are three objectives to be achieved on the model VRPMTTWPD, i.e, minimize the number of tours, total tour duration time, and a range of duration time of the langest and shortest tour. The number of tour represents capital cost that is mini-mized, labor cost and other operating costs. Total duration time represents vehicle operiational cost, e.g., fuel consumption. Total tour duration time represents the minimization of operational costs of vehicles, fuel samples. Generally, these objectives are usually found in the vehicle routing problem model. The third objective represents a balance total duration time of each tour. Suprayogi and Priyandari [13] solved this model by using genetic algorithm and tabu search.

Each of these goals is weighted W1, W2 and W3.

While, W1 > W2 > W3 reflects that the first goal has

greather priority than the second one, and the second goal has a greater priority than the third one. We set W1: 100000, W2 : 100, W3 : 0.00005 with the

Result and Discussion

In this paper, the system is defined as system that connected with finding set of tour for several vehicles in distributing products. This system consists of a depot, linehauls customers, and backhaul customers. Every activities starts from depot and ends to the depot. For every customer and depot, there is loading/unloading time. The unit measurement for loading/unloading time is same as unit measure-ment for customer’s demand. Figure 1 shows the representation of system structure. In a planning horizon, one vehicle can serve more than one customer starting linehauls customer and after that backhaul customer. One vehicle can serve more than one route, only same product each delivery, and only at customer’s time window.

Figure 1. System architecture

Backhauls can be defined as vehicle serves customer in a route apart from pick up activity and delivery activity. Delivery customers (linehauls customer) are served first before pick up customers (backhauls customer).Vehicle serves a set of routes in every tour, is called multiple trips, and returns to depot before serving others route. This condition can only be fulfilled if service time is in planning horizon. Vehicle goes to customer in a certain time window that has been stated before and also deterministic demand. This constraint makes vehicle waiting if it has arrived before the time windows. Time window is an interval time that customers provide to accept the service. In this research, there are loading and unloading times which respectively represent the time to move goods from warehouse to vehicle and just the opposite. The loading and unloading time will not exceed initial service time and the end of service time.

This model considers the customer’s priority which linehauls customer serves before backhauls custo-mer. The objective functions are to minimize the number of vehicles, minimize total tour completion time, and minimize range of duration time. We find the solution lexicographically or alphabetically. It means that the objective function are given priority consecutively, which the first objective has higher priority than the second objective and the third objective.

Decision variables are number of tours, customer’s sequence served in every route and tour, arrive time, earliest service time, latest service time, and departure time at every customer. The parameters are number of linehauls customer, a number of backhauls customers, linehauls customer’s demand, backhauls customer’s demand, distance, vehicle’s speed, time window, and planning horizon.

There are a lot of constraints in vehicles routing problem with backhaul, multiple trips, and time window (VRPB-MTTW):

(i) Every route starts and ends at depot

(ii) Planning horizon indicates the starting and the

ending of vehicle activity

(iii) Delivery demand and pickup demand are

(iv) Vehicle serves backhauls customer after

(v) Every customer can only be served once by one

(vi) The vehicle’s load must not exceed vehicle’s

(vii) Service time can only be started at earliest

time and before or equal with latest time

Range of Duration Time (RDT) is a difference between the longest tour duration time and the shortest tour duration time

, : number of linehauls customers’

posi-tions in route from tour

, : number of backhaul customers’ positions

, , : earliest departure time at node position

, , : latest departure time at node position

, , : starting time for service at node position

, , : earliest starting time for service at node

, , : latest starting time for service at node position in route from tour

, , : waiting time at node position in route

, : Total delivery load in route r from tour

, : Total pick-up load in route from tour

, , : Total load at position in route from

, , : Loading-unloading time at position in

, : travel time from node to : earliest time window at node

: latest time window at node : delivery demand at node with : pick up demand at node with

: vehicle capacity : service time

: number of linehauls customer : number of backhauls customer

RDT : difference between the longest tour duration time and the shortest tour duration time

Every , , location for certain , and refers to

To assure that every node can only visited exactly

once, every appears once at certain , and ,

except for . Therefore, this can be stated as:

From this equation onward, we use these following indexes instead they are stated differently.

Total delivery and pickup load for any route can be stated respectively as:

Total load in vehicle for any location can be stated recursively as:

The vehicle’s capacity constraint can be expressed in the following inequalities:

To make sure that linehauls customer must be served before backhaul customer, can be expressed in the following equality:

Earliest arrival time, starting time for service and earliest departure time at location can be determined by forward counting as follow:

The visibility of time window can be stated as:

for equation (15), (16) and (19) , , … , ,

Loading/unloading time at any node for linehauls customer is the total delivery demand at that node and as well as for backhauls customer, as follow:

Especially for node 0 (depot), loading/unloading time from depot and ends to depot can be stated as:

Latest arrival time time and latest departure time at any location is determined by backward counting as follow:

so that, the expression can be stated as: , , , , , (27)

For equation (26) and (27) , , … , meanwhile for equation (28)-(30) , , … , , Waiting time for any location is represented in the following expression: , , , , , , , , , , , , if , , , , , … , , 31 Tour duration time is defined as difference between the arrival time (starting time for service) at the depot for the first time and the departure time (ending time for service) at the depot for the last time. This can be expressed as: , , , , , , … , , The total tour duration time is a summation of all tour duration times stated as: ∑ (33)

Range of Duration Time (RDT) is defined as a difference between the maximum of tour duration time and the maximum of tour duration time, is formulated as follow: , , (34)

RDT will be set zero if there is only one vehicle to serve all customers. Every vehicle can only serve exactly one tour. Thus, number of vehicles used is equal to number of tours. This can be stated as: (35)

This model has three objectives preference struc-tures considered. For all strucstruc-tures, minimizing number of vehicles (NV) is always place as first objective. The second objective is minimizing the total duration time (TDT) and the last is minimizing range of duration time (RDT). Therefore, It can be formulated as: , , (36)

Various techniques both optimal and heuristics have been developed to solve the vehicle routing problem. Bullnheimer et al. [4] stated that the vehicle routing problem is a hard combinatorial problem with a computational combinatorial increased along the increasing size of the problem. Vehicle routing pro-blem is generally solved with heuristic and meta-heuristic approach e.g. 2 opt, 3 opt, simulated annea-ling, genetic algorithm, tabu search, ant colony optimization, etc.

Sequential insertion is the most often used method in solving vehicle routing problems. This is caused by the speed in delivering solution, easy to use and easily modified to handle a difficult constraint. Sequential insertion algorithm is used to generate the initial feasible solution. First, algorithm will generate a tour and the first route. Algorithm chooses linehauls customer by using predetermined rule. These rules are earliest deadline, earliest ready time, shortest time window, and longest travel time.

Steps of the sequential insertion algorithm are described as follows.

Input all the parameters and initialize the set of unassigned linehauls customer and the set of

unassigned backhauls customer . Go to step 1.

Create a tour and a route of this tour by setting

As long as there are unassigned linehauls customers , do this step. If all linehauls custo-mers have been

served, go to step 9. For and , choose

unassigned linehauls customers as seed customer

using predeter-mined rule. Then go to step 4.

Check the feasibility of time window for linehauls customer . If it is feasible, then insert customer and calculate the load after exit from customer . Then go to step 5. If time window is not feasible,

return to step 2 and create new tour ( ) and

starts from the first route ( ).

Update the information about tour and route that have been created. Check whether there is

unassigned linehauls customer . If unassigned

linehauls customer still exists, return to step 2.

Calculate tour duration time and route that has been created. Choose minimum tour duration time for

assigning backhauls customer ( ). Update

infor-mation about minimum tour duration that has been chosen. Then go to step 7.

Check unassigned backhauls customer . If all

has been served, then go to step 9. Otherwise, create

possible insertion for backhauls customer to

the existing route. Check the pickup demand for this route. If backhauls customer’s demand does not exceed vehicle’s capacity, then go to step 8. If it exceeds the vehicle’s capacity, then create new route,

Check the feasibility of time window backhauls customer. If it is feasible, backhauls customer can be inserted and calculate vehicle’s load. Then repeat step 7.

Calculate tour duration time for route that has been created. Choose minimum tour duration time. If all customers have been served, stop this step.

The result shows that these four rules have a contribution to the solution using sequential insertion. The rule of earliest deadline, earliest ready time, shortest time window, and longest travel time

respectively result 10 vehicles, 11 vehicles, 13 vehicles, and 13 vehicles. So we choose earliest deadline result as initial solution for ant colony optimization technique.

Ant Colony Optimization

This technique is modified from ant system which is developed by Dorigo and Stutzle [9]. Ant colony optimization (ACO) consists of three parts, i.e. initialization data, parameter and pheromone

matrix generating solution and updating the pheromone matrix. In this research, ACO algorithm uses one colony to generate customer’s sequence that will be served. Modification in ACO is done by adding the decoding process to generate solution based on VRPB-MTTW’s constraint. Decoding process assures that three objective functions can be achieved.

Initialization

First, ACO has to be set its parameter, i.e. number of

iteration, number of ants, , and . Next step,

calculate initial pheromone matrix by using follow-ing expression:

Initial pheromone matrix needs total duration time (TDT) that has been calculated from initial solution by sequential insertion algorithm. Visibility matrix shows the willingness of the ant to leave each customer. This constraint depends on the latest time window for any customer ( ). The matrix can be calculated by using following expression:

The decision making about combining customers is based on a probabilistic rule taking into account both the visibility and the pheromone information. First, arrange all the customers sequentially from line-hauls to backline-hauls customer. Lineline-hauls customer has the high priority than any backhauls customer. To select the next customer j for the kth ant at the

ith node, the ant uses the following probabilistic

Decoding Process

Decoding process is a calculating process to determine number of vehicles based on customer’s time window and vehicle capacity. From the initialization, we will get a sequence of all customers that will be served. Thus, we check the feasible time window and the load constraint for each customer. If it is not feasible, then we add node 0 (depot) after the customer. Flowchart of our decoding process for VRPBMTTW is shown in Figure. 2.

results number of vehicles, total duration tour, and range duration time. From those results, we choose one ant based on objective function that has been predetermined. First priority is number of vehicles. If the first criterion is same from all ants, we choose the second criterion that is the minimum total duration time. So, we do the same thing for the third criterion that is the minimum range of duration time.

Pheromone Update

Pheromone matrix has to be updated in order to make ants choosing the path that is frequently passed. We need total duration time to update the matrix. For the path that has not been passed by ant, we use the following formula:

Mean while, for the path that has been passed by ant uses the following formula:

We generate data based on number of backhauls customers and time window. For each data, we use random demand for each customer ranges from 1 to 10 and random distance with coordinate (0,0) to (540,540).We calculate the distance using Euclidean Metric for each customer. A set of data consists of 100 customers whom 50% backhauls customers. The time window varies from tight time window to wide time window. In detail, a tight time window inter-vals ranging from 10 to 50 minutes, while the wide time window ranges from 390 to 540 minutes. We use the mix time window ranging from 10 to 540 minutes and the horizon planning for depot ranges from 0 to 540 minutes.

We used Borland Delphi 2007 and executed on Intel Atom CPU N270 1,6 GHz with 1G DDRAM. Our aim is to find standard parameter settings in order to get good combination of these parameters for VRPBMTTW. Dorigo [8] suggested parameter that express the sensitivity to trace, =1, parameter that states the sensitivity to the desirability, 2 ≤ ≤ 5, and

parameter pheromone trail evaporation, ρ = 0.5 for

travelling salesman problem. From that information, we observed all possibilities to find the combination of these parameters. Finally, we suggested

We analyzed the algorithm performance with 95% confidence level and 10% error. To simplify the analysis, we use equation (1) to compare the results. This equation is totally different if it is compared to

the objective function. There is a contradiction between equation (1) and the objective function. In this case, we want to find the algorithm performance in easy way. So, we use weight for each criterion.

Figure 2 The flowchart of decoding process

Table 1. Experiment results using ACO with z,

Experiment Number of Vehicles

Mean 8.3333 1942.40 272.31 1034239 Standard

Column 5-7 in Table 1 present the results using modified ACO including number of vehicles, total tour duration time, and range of duration time. Column 8 is used to calculate the number of replica-tion by using the following formula:

The result shows that the algorithm has a consistency in solving VRPBMTTW.

We also compare the algorithm to the sequential insertion. The algorithm results better solution to the initial solution. The algorithm provide 8.3 vehicles in average, while the sequential insertion results 10 vehicles.

Four rules for selecting the seed customer in the sequential insertion algorithm are provided. These rules are earliest deadline, earliest ready time, shortest time window, and longest travel time. Figure 3 shows four improvement operator arrange-ments are provided.

Figure 4 shows a tour and schedule plan generated using earliest deadline criterion. The tour and schedule plan has information such as sequence of visiting customers, time window, linehauls demand, backhauls demand, arrival and departure time, service time, and travel time.

Figure 3. Input dialog box

Figure 4. An output showing tour and schedule plan

This paper has presented a new variant of the vehicle routing problem with backhauls including the characteristics such as multiple trips, and time windows. The multiple objectives are considered in this paper. An ant colony optimization technique is modified based on the characteristics. The initial feasible solution is generated using sequential insertion with different four seed customer. The computational experiments for others percentage of backhauls should be conducted to show the effectiveness and efficiency of the solution technique including the parameters proposed.

1. Bin, Y., Zhong-Zhen, Y., and Baozhen, Y., An

Improved Ant Colony Optimization for Vehicle

Routing Problem. European Journal of

Opera-tional Research 196, 2009, pp. 171–176.

2. Brandao, J. A., New Tabu Search Algorithm for

the Vehicle Routing Problem with Backhauls,

European Journal of Operational Research 173, 2006, pp. 540-555.

3. Bell, J. E., and McMullen, P. R., Ant Colony

Optimization Techniques for the Vehicle Routing

Problem. Advanced Engineering Informatics 18,

4. Bullnheimer, B., Hartl, R. F., and Strauss, C.,

An Improved Ant System Algorithm for the

Vehicle Routing Problem. Annals of Operation

Research 89, 1999, pp. 319-328.

5. Cho, Yuh-Jen., and Wang, Sheng-Der, A

Threshold Accepting Metaheuristics for the Vehicle Routing Problem with Backhauls and

Time Window. Journal of the Eastern Asia

Society for Transportation Studies,6, 2005, pp. 3022-3037.

6. Crispim, J., and Brandao, J., Reactive Tabu

Search and Variable Neighbourhood Descent Applied to the Vehicle Routing Problem with

Backhauls. 4th Metaheuristics International

Con-ference Porto, Portugal July 16-20, 2001.

7. Doerner, K., Gutjahr, W. J., Hartl, R. F.,

Strauss, C., and Stummer, C., Ant Colony Opti-mization in Multiobjective Portofolio Selection,

4th Metaheuristics International Conference,

8. Dorigo, M., MACS-VRPTW: A Multiple Colony

System for Vehicle Routing Problems With Time

Windows, Ant Colony Optimization,

Massa-chusetts Institute of Technology, London, 1999.

9. Dorigo, M., and Stützle, T., Ant Colony

10. Dorigo, M., and Blum, C., Ant Colony Optimiza-tion Theory: A Survey, Theoretical Computer Science. 344 (2-3), 2005, pp. 243-278.

11. Laporte, G., Gendreau, M., and Potvin, J.,

Classical and Modern Heuristics for the Vehicle

Routing Problem. Transactions in Operational,

12.Mong Sim, K., and Hong Sun, W., Ant Colony

Optimization for Routing and Load-Balancing:

Survey and New Directions. IEEE Transaction

on Systems, Man, and Cybernetics, 33(5), 2003, pp. 560-567.

13. Suprayogi, and Priyandari, Y., Vehicle Routing

Problem with Multiple Trips, Time Windows, and Simultaneous Delivery and Pickup Services.

Asia Pacific Industrial Engineering and Mana-gement System, 8, 2009, pp. 1543-1552.

14. Suprayogi, Vehicle Routing Problem: Definition,

Variants, and Application. Proceeding Seminar

Nasional Perencanaan Sistem Industri 2003

15. Tavakkoli-Moghaddam, R., Rabbani, M., Saremi,

A., and Safaei, N., Solving the Backhaul Vehicle

Routing Problem by Genetic Algorithms. 35th

International Conference on Computers and Industrial Engineering, 2005, pp.1905-1910.


Vehicle Coordinated Strategy for Vehicle Routing Problem with Fuzzy Demands

The vehicle routing problem with fuzzy demands (VRPFD) is considered. A fuzzy reasoning constrained program model is formulated for VRPFD, and a hybrid ant colony algorithm is proposed to minimize total travel distance. Specifically, the two-vehicle-paired loop coordinated strategy is presented to reduce the additional distance, unloading times, and waste capacity caused by the service failure due to the uncertain demands. Finally, numerical examples are presented to demonstrate the effectiveness of the proposed approaches.

1. Introduction

The vehicle routing problem (VRP) was first proposed by Dantzig and Ramser [1]. The VRP has since been the topic of many operational studies. VRP consists of designing efficient routes to serve a number of nodes with a fleet of vehicles. Each node is visited exactly once by one vehicle. The activity of the vehicle is bounded by certain constraints. Each vehicle starts at the depot and returns to the same depot after completing its task. Most VRP studies employ the vehicle uncoordinated strategy that is, there is no coordination between the vehicles, and each vehicle completes only its own task. There are many significant VRP results based on this case, including those of Clarke and Wright [2], Solomon [3], Laporte [4], Figliozzi [5], Sprenger and Mönch [6], Pillac et al. [7], Kou et al. [8], and Kou et al. [9].

The vehicle routing problem with fuzzy demands (VRPFD) is an extension of the VRP that is, the demand of each node is uncertain, subjective, ambiguous, and/or vague [10]. The VRPFD is widely employed for many real applications due to their numerous uncertainties, including garbage collection systems, product recall systems, and raw milk collection systems (collecting raw milk from dairy farmers for milk powder production enterprises). There are also several classical studies that refer to the VRPFD, such as Bertsimas [11], Cao and Lai [12], Kuo et al. [13], Kou and Lin [14], Kou et al. [15], Allahviranloo et al. [16], and Hu et al. [17]. The VRPFD typically assumes that the real value of a node’s demand is known when the vehicle reaches the node, whereas the vehicle’s route is planned in advance. After serving

nodes, the vehicle might not be able to service the

node once it arrives due to insufficient capacity. In such situations, if the vehicle uncoordinated strategy is employed, the vehicle must return to the depot and unload what it has picked up thus far and then return to the node where it had a “service failure” and continue to serve the remaining nodes. Thus, “additional distance” and “additional unloading times” are introduced due to the “service failure.” However, there are also vehicles with surplus capacity after completing their own tasks, introducing “waste capacity.” All of these cases result in increasing logistics cost. To the authors’ knowledge, few researchers have addressed the problem of minimizing the “additional distance” and “waste capacity,” let alone “additional unloading times,” in the VRPFD.

In this paper, vehicle coordinated strategy (VCS) is defined such that each vehicle finishes its own assigned task first then, if there is a vehicle with surplus capacity, the vehicle must help any vehicle that has not completed its own task according to the specified vehicle coordination rules [18, 19]. Only a few VRP studies have considered VCS. Shang and Cuff [20] considered a multiobjective vehicle routing heuristic for a pickup and delivery problem. They assumed that the fleet size is not predetermined and that customers are allowed to transfer between vehicles. These transfers can occur at any location and between any two vehicles. Yang et al. [21] proposed a mixed-integer programming formulation for the offline version of the real-time VRP and compared five rolling horizon strategies for the real-time version. To some extent their work is relevant to vehicle coordination. Liu et al. [18] proposed a simple general VCS for the VRP with deterministic demands. Lin [19] designed a VCS with single or multiple vehicle uses. The VCS is defined as allowing vehicles to travel to transfer items to another vehicle returning to the depot, provided that no time window constraints are violated. Sprenger and Mönch [6] studied a methodology to solve a cooperative transportation planning problem motivated by a real-world scenario found in the German food industry. Several manufacturers with the same customers but complementary food products share their vehicle fleets to deliver to their customers. They designed a heuristic to solve the problem. The results of extensive simulation experiments demonstrated that the cooperative setting outperforms the noncooperative one. Hu et al. [22] presented a feasible routing solution to accommodate the changes (such as customer’s demand changes, delivery time window changes, disabled roads induced by traffic accidents or traffic jams, and vehicle breakdowns) and to minimize the negative impacts on the existing distribution process in real-time VRP. They handle these disruptions by readjusting vehicle routes in real time to improve vehicles’ efficiency and enhance service quality. To a certain extent their work is relevant to vehicle coordination. However, all investigations assumed that the customers were uniformly distributed in certain regions and that the demands were deterministic. To the authors’ knowledge, few studies have employed the VCS in the VRPFD.

Thus, in this paper, the fuzzy reasoning constrained program model for VRPFD is formulated, and the hybrid ant colony algorithm is designed to minimize total travel distance. In particular, the two-vehicle-paired loop coordinated strategy (TVPLCS) is presented to reduce the “additional distance,” “additional unloading times,” and “waste capacity” caused by the service failure due to the uncertain demands. Finally, numerical examples are presented to demonstrate the effectiveness of the proposed approaches.

The remainder of this paper is organized as follows. In Section 2, the fuzzy reasoning constrained program model for VRPFD is formulated. In Section 3, we design a hybrid ant colony algorithm for VRPFD. In Section 4, in particular, we present the TVPLCS to minimize the “additional distance,” “additional unloading times,” and “waste capacity”. In Section 5, we give numerical examples to demonstrate the effectiveness of the proposed approaches. Finally, we summarize the contributions of this paper.

2. VRPFD Assumptions and Model

2.1. VRPFD Assumptions

In this paper, the VRPFD assumes that there is only one depot denoted by

nodes with fuzzy demands served by

vehicles. The locations of the depot and nodes are known. The fuzzy demand of each node