1 Introduction
The vehicle routing problem (VRP) is widely used in varieties of fields and achieves great success. It was firstly discussed by two famous operations research (OR) experts Dantzig and Ramser
[1]. After this pioneering work, the study of VRP problem exploded in academia and practice during the last six decades. VRP aims to find the optimal vehicle routings to visit a given collection of customers. Each vehicle starts from a depot, delivers the good to the customers, and finishes the delivery task at the same depot. The basic VRP problem only considers the capacity constriction of the vehicles. Besides the basic VRP, dozens of VRP variants have been studied to address the wide variety of conditions in real-world contexts, such as time windows, maximum route length, split delivery, heterogeneous fleet, etc. A comprehensive review on the VRP, its variants, formulation, and solution methods can be consulted in Braekers, et al.
[2] and Eksioglu, et al.
[3].
Triggered by the seminal work by Chao
[4], TTRP becomes one of the well-known VRP variants. TTRP is very common in city distribution, particularly in populated and intensive downtown. The accessibility restrictions against the use of big capacity vehicles to perform deliveries. So the big vehicle may decouples to two separate parts, and conduct the delivery by the mobile part. For example, technicians maintain municipal infrastructures in cities. However the pedestrian zones cannot be accessed by van. As a result, technicians must drive vans to the nearest stop area and walk to the destination
[5].
Table 1 compares the basic VRP problem and TTRP problem. In the basic VRP, an implicit assumption is that each vehicle could not be decoupled. However, in the TTRP problem, the complete vehicle is composed of a pure truck and a trailer. Due to the road and law restrictions, the complete vehicle may stop at a possible parking spot, and decouples to two parts, and visits the customer only by the truck part.
Table 1 Characteristics of the basic VRP and TTRP |
| Category | Basic VRP | TTRP |
| Vehicle | Identical pure trucks | Two types of vehicles: |
| (ⅰ) Pure truck |
| (ⅱ) Complete vehicle |
| Customer | Identical customers | Two kinds of customers: |
| (ⅰ) Truck customer (TC) |
| (ⅱ) Vehicle customer (VC) |
| Route | Identical pure trucks | Three types of routes: |
| (ⅰ) Pure vehicle route (PVR) |
| (ⅱ) Pure truck route (PTR) |
| (ⅲ) Complete vehicle route (CVR) |
Figure 1 illustrates a TTRP route plan using an example with 17 customers and 1 depot. Customer is represented by an integer between 1 and 17, and shown as a square or a circle. The depot is located in center and denoted by a black rectangle. The route plan has three routes, i.e., routes 1, 2 and 3. The arrows connects the customers, which display the visit order performed by the vehicles. The route 1 is a PVR traveled by a complete vehicle, depot depot. The route 2 is a PTR traveled by a pure truck, depot depot. The route 3 is a CVR consisting of a main tour, depot depot, and three sub-tours, , , and . In route 3, the main tour is connected by VCs and performed by a complete vehicle. The complete vehicle will decouple at sub-tour root, which is represented as a hollow square in Figure 1. The trailer will stop at the sub-tour root, and the split truck will visit the customers in sub-tour, and recouple with trailer at the same sub-tour root.
Figure 1 Illustration of a TTRP route plan |
Full size|PPT slide
The TTRP belongs to the category of NP-hard problems
[6]. It implies the meta-heuristic algorithms seems to be the only promising technique to trade-off the high-quality solutions and the reasonable computational time in large instances
[7].
Table 2 summarizes several studies. In the parameters column, the minimum parameters to perform these algorithms are given, but usually more parameters are needed to get better solutions. For example, Tabu search only has one parameter, i.e., tabu length. However, the Tabu search proposed by Scheuerer
[8] has other six parameters except for tabu length, which are neighborhood size, sampling size, tabu duration multiplier, shifting penalty adjuster, long-term penalty adjuster, and penalty term.
Table 2 Meta-heuristics for TTRP |
| Author | Meta-heuristics | Minimum Parameters |
| Chao[4] | TS | (ⅰ) Tabu list length |
| Scheuerer[8] |
| Shih and Yu[9] | SA | (ⅰ) Initial temperature |
| (ⅱ) Cooling schedule |
| | | (ⅰ) Restricted candidate list (RCL) of size |
Villegas, et al.[10]
Villegas, et al.[11] | Hybrid approach based on GRASP, VNS and PR | (ⅱ) Maximum infeasibility threshold |
| (ⅲ) Maximum number of pairs |
| | | (ⅳ) Distance threshold |
| | | (v) Size of the elite set of PR |
| Derigs, et al.[12] | Hybrid approach based on LS and LNS | (ⅰ) LS or LNS selection probability parameters |
| (ⅱ) The best deviation parameter |
| (ⅲ) Customer removal percentage |
| Wang, et al.[13] | BA | (ⅰ) Population size |
| (ⅱ) Frequency |
| (ⅲ) Pulse rate |
| (ⅳ) Loudness |
The performance of the meta-heuristics largely depends on the adjustment of the parameters in the algorithm. But the tune of control parameters is a time-consuming task. It is hard to find the best combination in most of the time. As the number of control parameters increases, the operations for tuning parameters increase exponentially
[14]. The cumbersome parameter adjustment process impedes the application of some mature meta-heuristics algorithms in the industry proposed the backtracking search algorithm (BSA)
[15, 16], which has only one control parameter (mixrate for crossover probability). And Song, et al.
[17] presented that this parameter was insensitive to its initial value. The relatively simple and effective algorithm structure quickly attracts many scholars to use BSA for solving the optimization problem after it being presented in 2013. Up to now, scholars have use it to solve a broad spectrum of practical problem, such as surface wave analysis
[17], allocation of multi-type distributed generators
[18], economic dispatch problem
[15, 19]. The results displayed that BSA is a very effective approach in different engineering problems. However, there is no literature on BSA for TTRP problem so far. Thus, this research gap motivates us to develop a backtracking search (BSA)-based meta-heuristic in a TTRP model. The reminder of this paper is structured as follows. Section 2 reviews the related TTRP literature. Section 3 describes a BSA-based meta-heuristic for TTRP problem. Section 4 presents the experimental results of our proposed BSA with three existing algorithms. Section 5 is the conclusions and future work.
2 Previous Works on TTRP Problem
TTRP is one of the most frequently encountered problem in city distribution, but it has not got the attention it deserves in academics communities. This section briefly presents the methodological contributions for TTRP in the literature after the first work on TTRP proposed by Chao
[4].
Concerning the inherent computational complexity for solving TTRP, the literature performed by exact methods is scare. The standard OR techniques branch-and-price (B & P) have been devised for the purpose of obtaining the optimal solutions for small TTRP. The B & P is a generalization of branch-and-bound with LP relaxations
[20]. Drexl
[21, 22] proposed two branch-and-price algorithms for Generalized TTRP, and solved the instances with 6 truck customers, 6 trailer customers and 6 transshipment locations. Parragh and Cordeau
[5] performed a study on TTRP with time windows, and also devised a branch-and-price approach for it. Unfortunately, their success for solving complicated real-life TTRP in limited.
Compared with exact algorithms for TTRP in excessively long computational time to obtain the optimal solutions, conventional heuristics and meta-heuristics appear to be more feasible for solving TTRP when the instance size becomes large. Starting with the saving algorithm
[23] for VRP, several heuristics have been proposed. The conventional heuristics consists two phase, which are route construction and route improvement. Chao
[4] proposed a constructive heuristic, which included a generalized assignment problem, route construction phase, as well as route improvement phase. Scheuerer
[8] developed T-Cluster heuristic and T-Sweep heuristic for TTRP. Caramia and Guerriero
[24] modeled TTRP as two sub-problems, namely the customer-route assignment problem and route definition problem, then solved them successively by the custom-tailor heuristic. Drexl
[22] presented a heuristic variant with a B&P approach.
The limitation of the conventional heuristic methods is that they are tailored to solve specific problems, which severely restricts their wider applications
[25]. Due to the versatility of metaheuristics, significant progress has been witnessed in the development of metaheuristic search strategies for the TTRP. At the early stage, several TS based solution methods to tackle the TTRP can be found in the literature. Chao
[4] developed a hybrid TS algorithm coupled with the deviation concept for TTRP. Another tabu search based procedure has been proposed by Scheuerer
[8]. Mirmohammadsadeghi and Ahmed
[26] addressed TTRP with stochastic demands, and developed a pure TS solution method for it.
In the last few years, a few other well-known meta-heuristic solution strategies have been devised and modified to solve TTRP. An SA meta-heuristic yielding high-quality solutions was proposed by Lin, et al.
[27]. Then this effective meta-heuristic was modified to solve the relaxed TTRP problem
[28] and TTRP with time windows
[29]. Parragh and Cordeau
[5] developed a meta-heuristic according to an adaptive-LNS for solving TTRP with time windows and demonstrated a high solving performance. In their meta-heuristic, the adaptive-LNS aimed to populate the column pool in the proposed B & P procedure. Mirmohammadsadeghi and Ahmed
[26] studied a practical instance for TTRP with stochastic demands, and solved it by SA, TS, and memetic algorithm methods respectively. The latter work performed by Wang, et al.
[13] introduced an adaptive bat algorithm for TTRP. Besides the pure meta-heuristics for TTRP, hybrid meta-heuristic approach (HMA) combining various algorithmic components has been developed in the last years. The HMA aims to explore the complementary advantages by combing different traditional approaches
[30]. For example, Villegas, et al.
[10] devised several versions of a HMA by hybridizing GRASP/VNS and PR methodologies for TTRP. Moreover, Villegas, et al.
[11] developed a construction-based meta-heuristics, which is a hybridization of GRASP and ILS approach. Derigs, et al.
[12] combined LNS and LS to exploit the advantages of neighborhood exploration. While BSA is successfully applied for capacity VRP
[31], as far as we can tell, BSA method have not been used up to now to solve the TTRP.
3 Methods
3.1 Backtracking Search Algorithm in the TTRP Model
This section will focus on presenting how the BSA solution technique is applied to solve TTRP. First the basic BSA algorithm is described. Then the encoding representation and constructive heuristic for building the initial population solutions are presented. Finally, local search for the improvement of solutions are discussed.
The BSA algorithm belongs to the category of population-based optimization techniques. The algorithm uses two unique concepts: Historical population and mapping matrix. In each iteration, the historical population guides the search towards the optimized results. It can well balance between exploration (global search) and exploitation (local search), and jump out of the local minima trap. In terms of exploitation, the mapping matrix further optimizes the current solution. More detailed algorithm introduction please refer to the literature Civicioglu
[16]. In the study of the TTRP problem, each individual in the population represents a vehicle routing plan. There are two selection processes for BSA, called Selection-Ⅰ and Selection-Ⅱ. Selection-Ⅰ is used to select historical populations before producing new trial populations. Selection-Ⅱ achieves selection of the better individuals after the generation of the test population. The solution process of the BSA approach is presented in
Figure 2. The core part is composed of five steps, which are: Initial population, selection-Ⅰ, mutation, crossover and selection-Ⅱ.
Figure 2 Flowchart of BSA algorithm |
Full size|PPT slide
Step 1 Initialization population
The population of the BSA algorithm consists of the current population and the historical population . The and are initialized by Equation (1) and Equation (2).
where , denotes the population size. denotes uniform distribution. and are matrix, and is the dimension of data set. represents the value of variable in individual in the population. indicates the lower bound of the search space. Similarly, indicates the upper bound. is fitness function. evaluates the fitness function and selects the global optimal solution. The corresponding individual population of is .
Step 2 Selection-Ⅰ
The selection of historical populations is redefined in each iteration by the if-then rules. The algorithm idea is shown in Equation (6):
where and follow uniform random numbers. indicates the update operations. The BSA algorithm has memory and randomly selects a population in the previous generation and marks it as a historical population until the population is updated. In the next step, the sequence of individuals in the historical population will be changed by Equation (7):
In this stage, the historical population
is selected for updating. If
, historical populations
are guided by current populations. If
, keep the historical population
unchanged. And
can be guided by any current or previous historical population, which greatly improves the global search capability of the BSA. It has a memory to store a previous population that defines the search direction
[32].
Step 3 Mutation and crossover
The BSA algorithm generates trial populations through crossover and mutation strategies. The crossover strategy will produce the initial pattern of the trial population. To obtain the trail population, we use Equation (8) for mutation:
where
is the control parameter.
, and it controls the search direction matrix
and its magnitude.
as recommended by Civicioglu
[16] and
.
The crossover strategy of BSA will produce the final trail population. The mapping matrix was introduced in the cross strategy. The algorithm 1 is used to obtain the mapping matrix. The crossover probability in row 4 is the only control parameter in the algorithm, which controls the number of individuals applying the crossover strategy in the trail population.
Algorithm 1 Generation of mapping matrix
Initialize the mapping matrix
if then
for do
end for
else
for do
end for
end if
Through the mapping matrix and the direction matrix , a new trail population is generated and the population is crossed, see Equation (9):
The definition of the parameter in Equation (9) is the same as Equation (8). Finally, after the crossover is completed, may include non-feasible solutions. If there is such an element, a value is randomly selected within the boundary of the feasible region to replace this element, so as to guarantee that the individuals in the population are all feasible solutions.
Step 4 Selection-Ⅱ
This step compares the Dist of the and the and updates the population based on Equation (10). For the TTRP optimization problem, selection Ⅱ can be described as:
where is the trail population, is the corresponding initial population, and is the fitness value. Based on the greedy selection rule, if trail individuals have the lower travelling distance (TD) in the TTRP, then are retained. Repeat Step 2 to Step 4 until the termination criterion is reached.
3.2 Encoding Representation and the Initial Population Solutions
The original BSA algorithm is proposed for the continuous optimization problem in continuous space. The TTRP problem is a combinatorial optimization problem in discontinuous space, and the solution space needs to be reconstructed. Non-negative integer coding is used to represent the solution space. A feasible solution representation is constructed by a permutation vector , where denotes the route that serves customers. Assuming the vehicle's route plan is shown in Figure 1, so solution representation of TTRP is presented in Figure 3. In Figure 3, TCs are highlighted in grey background. For VCs, they may be visited by a pure truck or by a complete vehicle. If visited by a pure truck, we set the service vehicle type equal to 1. Otherwise, the service vehicle type equal to 0.
Figure 3 Solution representation of TTRP |
Full size|PPT slide
In this study, the initial population TTRP solutions are constructed by using a T-sweep procedure, which is developed by Scheuerer
[8]. T-sweep is a sweep-based heuristic
[33], which follows cluster-first and route-second principle. It can produce good initial feasible solutions in short computational time.
At the clustering stage, the seed customer is selected as the first customer. Then the customer who has the smallest angle with the first customer is joined as the same clustering. The procedure is repeated until the vehicle capacity constraint is violated or all customers have been assigned in a cluster.
At the route stage, a TTRP is then solved in each group. Routes are constructed up to complete vehicle utilization. Hence, due to the capacity, complete vehicles have an advantage over pure trucks in the route construction. The unserved customers are maintained in an ejection pool. Then the one, who has the biggest Clark-Wright saving
[23] is selected to try to insert into the existing solution. In the construction of CVR, if the VC is selected to insert into a route, it will be shifted into the just one main-tour. And if the TC is selected to insert into route, it will be added into existing sub-tours or a new sub-tour. The VC will serve as a root for the new generated CVR sub-tour. If all available vehicles are assigned into the routes, the last route is permitted to become infeasible. This process is terminated until no unserved customers left.
3.3 Local Search Procedure of the Trial Population
Local search is used to repeatedly improve a set of initial populations by local changes. A blend of four well-known neighborhood structures have been implemented and their description is given as follows. If a solution with lower TD is found in the neighborhood of the current solution, it works by replacing the current best solution. In the next generation, the local search starts from the new generated better solution. The iterations continue until no better solution is found.
3.3.1 Exchange/Relocate Move
It is the intra-route moves proposed by Savelsbergh
[34]. The exchange move exchanges the selected customers within a route. As shown in
Figure 4, two selected VCs, i.e., VC 4 and VC 13, are exchanged within route 1. The route 1 is updated from depot
depot
depot. The service vehicle types of two VCs keep unchanged. The relocate move shifts a customer within a route. As seen in
Figure 5, in route 2, VC 12 is inserted between depot and VC 17. The route 2 is updated from depot
depot to depot
depot. The service vehicle type of VC 17 keeps unchanged.
Figure 4 Solution updated by exchange move in TTRP |
Full size|PPT slide
Figure 5 Solution updated by relocate move in TTRP |
Full size|PPT slide
3.3.2 Swap/Shift Move
In the swap move, it chooses two customers from any two routes randomly and swap the positions. It is note that TC in PTR is not allowed to swap with VC in CVR, VC in CVR only swaps with VC in other CVR, and TC in CVR is not allowed to swap with VC in other CVR. As indicated in Figure 6, VC 5 in route 1 swaps VC 1 in route 3. The route 1 is updated from depot depot to depotdepot. The main tour in route 3 is updated from depotdepot to depot depot, and the sub-tour 1 in route 3 is updated from . The service vehicle types of VC 1 and VC 5 keep unchanged. In the shift move, it randomly selects a route, and picks a customer, and then shifts it to a different route. As depicted in Figure 7, VC 13 in route 1 is shifted between VC 12 and depot route 2. The route 1 is updated from depot depot to depotdepot. The route 2 is updated from depot depot to depotdepot. The service vehicle types of customer 13 is changed from VC in route 1 to TC in route 2.
Figure 6 Solution updated by swap move in TTRP |
Full size|PPT slide
Figure 7 Solution updated by shift move in TTRP |
Full size|PPT slide
3.3.3 Relocate-Sub-Tour Move
It is a TTRP-specific move proposed by Derigs, et al.
[12]. It shifts the sub-tour in a CVR either to a PVR or to a different CVR. In
Figure 8, the sub-route 1 is detached from route 3 and shifted route 1. Now route 3 only consisted of 1 main tour and 2 sub-tours. The route 1 is updated from PVR route depot
depot to CVR route, which includes a main tour, depot
depot, and one sub-tour,
.
Figure 8 Solution updated by relocate-sub-tour move in TTRP |
Full size|PPT slide
3.3.4 Switch-Vehicle-Type Move
It is also a TTRP-specific move proposed by Lin, et al.
[27]. This move changes the service vehicle type for customer. For the customer visited by a complete vehicle, it will transfer the service vehicle type to the pure truck. For the customer performed by a pure truck, it will transfer the service vehicle type to the complete vehicle. In
Figure 9, we change the service vehicle type for VC 14 from a pure truck to a complete vehicle. The main tour in route 3 is updated from depot
depot to depot
depot, and the sub-tour 1 in route 3 is updated from
to
.
Figure 9 Solution updated by switch-vehicle-type move in TTRP |
Full size|PPT slide
4 Computational Experiments and Discussion
The proposed BSA was implemented in a JDK 7 platform and tested on a laptop equipped with an Intel i5-7Y54 CPU clocked at 1.61 GHz with 8 G of RAM. We perform 10 runs of the BSA for each instance. The parameter settings of BSA is as follows. The first parameter is the mix rate for the crossover process, we set it to be 0.9. The second parameter is the population size, we set it to be 50. The third parameter is the maximum number of generation loop, we set it to be 20, 000.
4.1 Introduction of the Benchmark Sets
The benchmark problem of TTRP, as presented in Chao
[4], which can be downloaded from
http://140.118.201.168/ttrp/. This well-known benchmark instances were developed based on Christofides, et al.
[35] instances, referred to as the CMT test-bed. The main characteristics of Chao's benchmark problem are presented in
Table 3. This benchmark problem consists of 21 instances, which are named CMTX-
. Here,
denotes customer size and
denotes fraction of truck customers.
=1, 2, 3, 4, 5, 11, and 12 represents customer size is 50, 75, 100, 150, 199, 120, and 100, respectively.
=1, 2, 3 represents the proportion of truck customers is 25%, 50% and 75%, respectively.
Table 3 Summary Characteristics for Chao's TTRP dataset |
| Instance | customers | Truck | Trailer | Ratio of demand to capacity |
| VC | TC | Number | Capacity | Number | Capacity |
| CMT1-1 | 50 | 38 | 12 | 5 | 100 | 3 | 100 | 0.971 |
| CMT1-2 | 50 | 25 | 25 |
| CMT1-3 | 50 | 13 | 37 |
| CMT2-1 | 75 | 57 | 18 | 9 | 100 | 5 | 100 | 0.974 |
| CMT2-2 | 75 | 38 | 37 |
| CMT2-3 | 75 | 19 | 56 |
| CMT3-1 | 100 | 75 | 25 | 8 | 150 | 5 | 100 | 0.911 |
| CMT3-2 | 100 | 50 | 50 |
| CMT3-3 | 100 | 25 | 75 |
| CMT4-1 | 150 | 113 | 37 | 12 | 150 | 6 | 100 | 0.931 |
| CMT4-2 | 150 | 75 | 75 |
| CMT4-3 | 150 | 38 | 112 |
| CMT5-1 | 199 | 150 | 49 | 17 | 150 | 9 | 100 | 0.923 |
| CMT5-2 | 199 | 100 | 99 |
| CMT5-3 | 199 | 50 | 149 |
| CMT11-1 | 120 | 90 | 30 | 7 | 150 | 4 | 100 | 0.948 |
| CMT11-2 | 120 | 60 | 60 |
| CMT11-3 | 120 | 30 | 90 |
| CMT12-1 | 100 | 75 | 25 | 10 | 150 | 5 | 100 | 0.903 |
| CMT12-2 | 100 | 50 | 50 |
| CMT12-3 | 100 | 25 | 75 |
4.2 Summary of the Results for Chao's TTRP Dataset
As mentioned by Wang, et al.
[13], the original link
http://www.cma.edu.tw/iming/research/ ttrp for Chao
[4] test problem is broken now. Current data files are stored online at
http://140. 118.201.168/ttrp/. However, instance 16–21 were modified in this available website. Then, SA algorithm proposed by Lin, et al.
[27], hybrid GRASP
ILS designed by Villegas, et al.
[11], self-adaptive bat algorithm developed by Wang, et al.
[13] used this modified benchmark to measure the performance of the proposed algorithms, see
Table 4 for the detailed description of these three approaches.
Table 4 The three meta-heuristics in the literature |
| Symbol | Meta-heuristics | Author | Description |
| L-2009 | Simulated annealing | Lin, et al.[27] | Pure SA framework with |
| various types of local |
| search operator. |
| V-2013 | Hybrid GRASP×ILS | Villegas, et al.[11] | ⅰ. A hybrid GRASP ILS metaheuristic |
| is used to produce a pool of routes |
| ⅱ. The routes becomes columns |
| in a set-partitioning problem. |
| ⅲ. A mixed integer programming optimizer |
| is applied to improve the solutions. |
| W-2018 | self-adaptive bat algorithm | Wang, et al.[13] | Pure bat algorithm framework |
| with five types of local search |
| operator, combing with a |
| self-adaptive tuning strategy |
The inharmonious run times of algorithm will complicates comparison
[36]. It is found that L-2009, V-2013 and W-2018 perform their algorithms 10 times on each instance, and obtained the best solution and average solution. However, D-2013 obtained best solution of 5 from 200K runs, and obtained average solution of 5 from 100K runs. A fair comparison could be performed as the same runs were executed by previous paper. So, the results from L-2009, V-2013, and W-2018 were used for comparison.
4.3 Results Comparison for Different Algorithms
This section discusses the performance of the BSA algorithm. To evaluate the performance, the results obtained from L-2009, V-2013, W-2018 are compared with the results produced by the proposed BSA, which is depicted in Table 5.
Table 5 Results for the Chao[4] data set |
| Problem | L-2009 | V-2013 | W-2018 | Proposed BSA |
| instance | | BKS | Best TD | Avg. TD | Avg. Time | Best TD | Avg. TD | Avg. Time | Best TD | Avg. TD | Avg. Time | Best TD | Avg. TD | Std. | variation(%) | Avg. Time |
| CMT1-1 | 50 | 564.68 | 566.82 | 568.86 | 6.80 | 564.68 | 564.82 | 1.32 | 564.68 | 564.85 | 0.52 | 564.68 | 565.83 | 3.31 | 0.585% | 1.69 |
| CMT1-2 | 50 | 611.53 | 612.75 | 617.48 | 6.67 | 611.53 | 612.38 | 1.34 | 611.53 | 614.47 | 0.78 | 611.53 | 612.64 | 2.07 | 0.337% | 1.58 |
| CMT1-3 | 50 | 618.04 | 618.04 | 620.50 | 5.59 | 618.04 | 618.04 | 1.09 | 618.04 | 618.04 | 0.73 | 618.04 | 618.04 | 0.00 | 0.000% | 1.25 |
| CMT2-1 | 75 | 798.53 | 808.84 | 817.71 | 16.32 | 798.53 | 798.53 | 2.93 | 799.78 | 802.43 | 1.21 | 801.90 | 805.88 | 8.26 | 1.024% | 3.59 |
| CMT2-2 | 75 | 839.62 | 839.62 | 858.95 | 14.42 | 839.62 | 839.62 | 2.60 | 839.62 | 840.69 | 1.68 | 840.94 | 842.64 | 4.30 | 0.510% | 3.28 |
| CMT2-3 | 75 | 930.64 | 934.11 | 942.60 | 13.65 | 942.26 | 947.95 | 2.81 | 937.31 | 939.41 | 1.48 | 941.12 | 941.74 | 0.95 | 0.101% | 3.25 |
| CMT3-1 | 100 | 830.48 | 830.48 | 838.50 | 24.96 | 830.48 | 830.55 | 13.77 | 830.48 | 835.19 | 3.59 | 830.48 | 833.74 | 4.37 | 0.524% | 6.47 |
| CMT3-2 | 100 | 870.94 | 875.76 | 882.70 | 24.03 | 870.94 | 872.36 | 7.00 | 874.46 | 877.28 | 3.82 | 872.77 | 877.56 | 5.55 | 0.633% | 6.55 |
| CMT3-3 | 100 | 912.02 | 912.64 | 921.97 | 21.75 | 914.23 | 914.23 | 8.03 | 914.23 | 919.31 | 3.51 | 914.23 | 920.91 | 6.09 | 0.662% | 6.96 |
| CMT4-1 | 150 | 1036.2 | 1053.90 | 1074.38 | 63.61 | 1036.20 | 1037.83 | 30.79 | 1045.66 | 1047.83 | 10.72 | 1051.46 | 1058.14 | 9.84 | 0.930% | 17.62 |
| CMT4-2 | 150 | 1091.91 | 1093.57 | 1108.88 | 60.33 | 1092.22 | 1093.29 | 25.20 | 1093.45 | 1103.43 | 9.23 | 1097.70 | 1104.77 | 8.81 | 0.797% | 18.98 |
| CMT4-3 | 150 | 1149.41 | 1155.44 | 1166.59 | 51.70 | 1149.75 | 1149.95 | 28.77 | 1154.06 | 1160.65 | 14.26 | 1159.81 | 1167.32 | 8.37 | 0.717% | 19.95 |
| CMT5-1 | 199 | 1284.71 | 1320.21 | 1340.98 | 119.56 | 1285.78 | 1287.41 | 86.15 | 1302.63 | 1305.92 | 24.32 | 1303.84 | 1309.23 | 5.41 | 0.413% | 37.65 |
| CMT5-2 | 199 | 1333.66 | 1351.54 | 1367.91 | 113.75 | 1333.66 | 1336.62 | 28.49 | 1340.33 | 1353.66 | 28.32 | 1349.03 | 1369.41 | 18.55 | 1.355% | 38.84 |
| CMT5-3 | 199 | 1416.51 | 1436.78 | 1454.91 | 93.87 | 1416.51 | 1418.52 | 36.91 | 1423.91 | 1435.32 | 38.20 | 1427.23 | 1447.26 | 15.83 | 1.094% | 45.98 |
| CMT11-1 | 120 | 1000.84 | 1004.47 | 1007.26 | 41.46 | 1000.84 | 1002.19 | 10.76 | 1004.47 | 1016.84 | 5.43 | 1004.47 | 1012.28 | 5.75 | 0.568% | 14.16 |
| CMT11-2 | 120 | 1026.17 | 1026.88 | 1035.23 | 38.81 | 1026.17 | 1026.33 | 10.61 | 1027.43 | 1030.97 | 5.78 | 1030.75 | 1034.08 | 2.95 | 0.285% | 11.59 |
| CMT11-3 | 120 | 1098.15 | 1099.09 | 1110.13 | 31.34 | 1100.84 | 1106.51 | 10.70 | 1099.36 | 1108.55 | 5.52 | 1100.59 | 1107.51 | 4.31 | 0.389% | 11.16 |
| CMT12-1 | 100 | 812.69 | 814.07 | 823.01 | 29.58 | 812.69 | 814.05 | 4.86 | 812.69 | 819.47 | 3.70 | 813.01 | 819.41 | 5.94 | 0.725% | 6.29 |
| CMT12-2 | 100 | 848.12 | 855.14 | 859.06 | 28.47 | 848.12 | 849.31 | 5.39 | 848.12 | 853.06 | 2.87 | 850.09 | 854.75 | 4.87 | 0.570% | 6.68 |
| CMT12-3 | 100 | 909.06 | 909.06 | 915.38 | 24.03 | 909.06 | 909.06 | 6.02 | 909.06 | 909.83 | 4.60 | 909.06 | 912.35 | 2.69 | 0.295% | 6.45 |
| BKS | 4 | | | 15 | | | 8 | | | 5 | | | | |
| Avg.cost | | 968.24 | | | 953.79 | | | 959.87 | | | 961.18 | | | |
| Avg.time(min) | | | 39.56 | | | 15.50 | | | 8.11 | | | | | 12.86 |
| BRE | 0.59% | | | 0.09% | | | 0.29% | | | 0.47 % | | | | |
| ARE | | 1.61% | | | 0.22% | | | 0.78% | | | 0.87 % | | | |
| Note: a, b and c mean BKS obtained by L-2009, V-2011 and D-2013, respectively. "std" is standard deviation. Bold values are the corresponding algorithm obtain the BKS. |
The first column is divided into three sub-columns. The "Number" sub-column presents the identifier of each instance. The "n" sub-column denotes the number of customers in each instance. The "BKS" sub-column indicates the best known solution produced in the literature. The next columns display the results produced by L-2009, V-2013, W-2018, and our proposed BSA algorithm. In each case, column "Best TD" and "Avg. TD" present the best solutions and average solutions reported by the corresponding algorithm. The last column "Avg. Time" show the required average computational time in 10 runs measured in minutes to solve the instance.
Table 5 is used is benchmark the performance of proposed BSA and three existing algorithms in terms of two criteria: Solution quality and computational time. First, solution quality of the algorithms is compared in the following (a) and (b).
(a) The "NBKS" row represents the number of BKS obtained in each algorithm. The algorithms can be sorted according to NBKS: L-. The L-2009 and our proposed BSA have the similar abilities to obtain the BKS of TTRP. The row "Avg. cost" presents the average solution cost and average computational time found by the corresponding algorithm in 10 runs over 21 instances. The Avg. cost leads to the same hierarchy as NBKS: L-.
(b) The "BRE" row is the best relative error to BKS, and the "ARE" row is the average error to BKS
[37], see Equations (11) and (12).
If the algorithms are ordered by BRE, the sequence is L- . If the algorithms are ranked based on ARE: L-.
The box and whisker plot is a visualization way to explore the consistency and reliability of the results produced by BSA, which is presented in Figure 10. It should be noted that all the TD in 10 runs have been normalized to their mean values for easy comparisons among 21 instances. Figure 10 presented that the results obtained by BSA are rather consistent and all maximum TD are found to be within 0%3.02% from the mean values. The column "Std." and "Coefficient of variation (%)" presented in Table 5 as a supplement to the box plots in Figure 10. The "Coefficient of variation (%)" column presents the proportion that the standard deviation is divided by the mean value so that difference in 21 instances can be observed.
Figure 10 The variance in box plots for Chao[4] instances |
Full size|PPT slide
The row "Avg. time (min)" in
Table 5 shows the average computational time found by the corresponding algorithm in 10 runs for 21 instances. In order to conduct a fair comparison, it is necessary to remove the machine relative speeds. The computer configurations in previous work are presented in
Table 6. The performance of the corresponding computer configuration is depicted in the third column "CPU index" of
Table 6. The CPU index is obtained from PASSMARK, which is a well-known public website to benchmark CPU and memory performance. High value of the CPU index means the faster CPU performance. Note that the specific processor in Villegas, et al.
[11] is not recorded, we use the average CPU index of model Q6700, Q8400, and Q9400. Using the computer configuration of L-2009 as the base line, the scaling factors of V-2013, W-2018 and proposed BSA are presented in the "scaling factor" column of
Table 6.
Table 6 Scaling factor for computational time |
| Algorithm | Computer configuration | CPU index | Scaling factor |
| L-2009 | Pentium IV 1.5 GHz | 291.94 | 1 |
| V-2013 | Intel Core 2 Quad processor 2.66 GHz (specific processor unknown) | 3276 | 11.22 |
Table 7 compares the original computational time (left figure) and scaling computational time (right figure).
Figure 11 is the visualization of average computational time for seven problem sizes. According to the original computational time, the algorithms are sorted by:
. Based on the scaling computational time, it leads to the hierarchy:
. As mentioned by Tan, et al.
[38], the computational time should not be viewed as a major obstacle in solving VRP variants. With the development of hardware upgrade and parallel computing techniques, it will reduce the computational time dramatically, and the routing solutions plan is more important than computational time
[39].
Table 7 Original computational time and scaling computational time for different algorithms |
| Problem | L-2009 | V-2013 | W-2018 | Proposed BSA |
| Instance | | Original. Time | Original. Time | Scaling time | Original. Time | Scaling time | Original. Time | Scaling time |
| CMT1-1 | 50 | 6.80 | 1.32 | 14.81 | 0.52 | 23.79 | 1.69 | 21.86 |
| CMT1-2 | 50 | 6.67 | 1.34 | 15.03 | 0.78 | 35.69 | 1.58 | 20.50 |
| CMT1-3 | 50 | 5.59 | 1.09 | 12.23 | 0.73 | 33.40 | 1.25 | 16.23 |
| CMT2-1 | 75 | 16.32 | 2.93 | 32.87 | 1.21 | 55.36 | 3.59 | 46.44 |
| CMT2-2 | 75 | 14.42 | 2.60 | 29.17 | 1.68 | 76.86 | 3.28 | 42.40 |
| CMT2-3 | 75 | 13.65 | 2.81 | 31.53 | 1.48 | 67.71 | 3.25 | 42.12 |
| CMT3-1 | 100 | 24.96 | 13.77 | 154.50 | 3.59 | 164.24 | 6.47 | 83.66 |
| CMT3-2 | 100 | 24.03 | 7.00 | 78.54 | 3.82 | 174.77 | 6.55 | 84.81 |
| CMT3-3 | 100 | 21.75 | 8.03 | 90.10 | 3.51 | 160.58 | 6.96 | 90.02 |
| CMT4-1 | 150 | 63.61 | 30.79 | 345.46 | 10.72 | 490.44 | 17.62 | 227.95 |
| CMT4-2 | 150 | 60.33 | 25.20 | 282.74 | 9.23 | 422.27 | 18.98 | 245.64 |
| CMT4-3 | 150 | 51.70 | 28.77 | 322.80 | 14.26 | 652.40 | 19.95 | 258.15 |
| CMT5-1 | 199 | 119.56 | 86.15 | 966.60 | 24.32 | 1112.64 | 37.65 | 487.14 |
| CMT5-2 | 199 | 113.75 | 28.49 | 319.66 | 28.32 | 1295.64 | 38.84 | 502.60 |
| CMT5-3 | 199 | 93.87 | 36.91 | 414.13 | 38.20 | 1747.65 | 45.98 | 594.94 |
| CMT11-1 | 120 | 41.46 | 10.76 | 120.73 | 5.43 | 248.42 | 14.16 | 183.20 |
| CMT11-2 | 120 | 38.81 | 10.61 | 119.04 | 5.78 | 264.44 | 11.59 | 150.03 |
| CMT11-3 | 120 | 31.34 | 10.70 | 120.05 | 5.52 | 252.54 | 11.16 | 144.35 |
| CMT12-1 | 100 | 29.58 | 4.86 | 54.53 | 3.70 | 169.28 | 6.29 | 81.40 |
| CMT12-2 | 100 | 28.47 | 5.39 | 60.48 | 2.87 | 131.30 | 6.68 | 86.43 |
| CMT12-3 | 100 | 24.03 | 6.02 | 67.54 | 4.60 | 210.45 | 6.45 | 83.43 |
| Avg. time | | 39.56 | 15.50 | 173.93 | 8.11 | 370.95 | 12.86 | 166.35 |
| Note: time is measured in minutes. |
Figure 11 The corresponding computational time of algorithms for seven problem sizes |
Full size|PPT slide
5 Conclusions and Future Work
TTRP is one of the most frequently encountered problem in city distribution, particularly in populated and intensive downtown. However, it has not been given sufficient attention in the literature. This study develops an easy and effective BSA algorithm TTRP problem. This solution technique is built on the pure BSA meta-heuristic framework proposed by Civicioglu
[11]. In the proposed approach, we first generate a set of feasible initial solutions by applying a T-sweep heuristic. Then we use a modified BSA which considers four well-known neighborhood structures. The proposed BSA is benchmarked against three existing algorithms on Chao's benchmark test problem. The results demonstrate the effectiveness of the BSA algorithm, and high-quality solutions are produced within reasonable computational time. Future work will extend BSA to solve TTRP problem with other practical constraints, such as time windows, multiple periods, and multiple objectives. In addition, a case study can also be piloted for the feasibility of real-world applications.
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
PDF(699 KB)
Table 1 Characteristics of the basic VRP and TTRP
Figure 1 Illustration of a TTRP route plan
