# Optimal Method for Allocation of Tractors and Trailers in Daily Dispatches of Road Drops and Pull Transport

Authors: Hao Chen; Wenxian Wang; Birong Cheng; Min Zhou
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

The domestic road drop and pull transportation system allows only tractors and semitrailers. In this mode, any tractors can only run with one semitrailer at a time or with no load. By optimizing the tractor scheduling plan, the no-load mileage of the tractor can be reduced, which can improve the efficiency and reduce the number of tractors. In this article, we have developed an optimization model for the tractor routing scheme to minimize the total cost of the drop and pull transportation system, which can limit the total number of tractors because the tractor can transport as many semitrailers to the destination as possible within the time window. Focusing on this mixed integer nonlinear problem, an improved ant search algorithm is designed. Finally, with Sichuan’s Anji Logistics Enterprise as the background, this tractor scheduling optimization model is applied to an ideal network and a real scenario. The results show that the optimized system reduces total cost by approximately18.7% and the ratio of tractors to semitrailers is approximately 1 : 3.31.


---

## Body

## 1. Introduction

Drop and pull transport (DPT) refers to an organization method in which tractors drop off and hang designated trailers at cargo operation points according to an established plan. With the steady growth of the domestic economy and the increasing demand for freight transport year by year, DPT has ushered in rapid development as an efficient transportation method that greatly reduces energy consumption and carbon emissions. In 2009, the Ministry of Communications, the National Development and Reform Commission, and other departments issued the “Notice on Promoting the Development of Drop and Pull Transport,” which provided policy support for vehicle licensing, insurance, station construction, and funding arrangements, and it officially launched the pilot work of DPT in 2010. As of 2020, there were 11.7154 million trucks nationwide, of which 3.1084 million were tractors and 3.3463 million were trailers. The ratio of tractors to trailers is approximately 1 : 1.07.However, in European and American countries where the DPT is relatively mature, the ratio of tractors to trailers engaged in freight logistics reached 1 : 3 in 2007. Even in countries with small areas, such as Southeast Asia, the ratio of tractors to trailers reached approximately 1 : 5 in 2012. The excessively high number of tractors not only increases the cost of vehicle purchasing but also leads to the idling of tractors in daily drop and pull transport. Therefore, these problems prompted this article to seek an optimization method for the configuration of tractors and trailers to improve the organization and management level of DPT. A reasonable ratio of the number of tractors and trailers can not only reduce the cost of DPT but also effectively increase the utilization rate of tractors.Due to the existing policies of restricting the connected form of drop and pull transport in China, the connected form of the tractor towing trailer shown in Figure1(a)is not allowed on Chinese roads, which allow only the tractor towing semitrailer, as shown in Figure 1(b); that is, the part with power is not allowed to load. Therefore, the research and application of drop and pull transport in China is quite different from that in Europe and America. This paper mainly studies the problem of the proportion of tractors and semitrailers in China and proposes a path optimization method to calculate the optimal proportion of tractors and semitrailers in the transportation network.Figure 1
Two types of connected forms of vehicles for drop and pull transport.
(a)
Tractor and trailer model(b)
Tractor and semitrailer modelThe problem is similar to the vehicle routing path problem in nature. The existing models and algorithms have good performance in dealing with the vehicle routing optimization problem. Under the policy requirements of our country, the semitrailer to be delivered in the transportation network can only be delivered by one tractor at the same time, and the operation state (full load or no load) between the tractor and the station is determined according to the operation path of the tractor and the transportation demand of the semitrailer. The goal of this paper is to determine the routing scheme of all tractors transporting semitrailers to minimize the number of tractors required to be configured under the condition of completing the semitrailer distribution requirements. Each semitrailer to be delivered (with a time window constraint) is regarded as an object requiring tractor service. Which semitrailers are delivered to each tractor within a working day depends on (i) the starting and ending stations and (ii) the delivery time window requirements of these semitrailers. Under the condition of the lowest operating cost of the coupling system, the required tractor and semitrailer is the optimal proportion. The actual case results show that this method is suitable for the optimization of the number of tractors and semitrailers in the transportation network. The main contributions of this paper are as follows:(1)
The investigation conducted in this paper is a step forward in the research of the proportion of swing and pull transportation vehicles. From the perspective of tractor scheduling optimization, this method transforms the optimal proportion of tractors and semitrailers into the proportion of tractors and semitrailers under the condition of the optimal running path of tractors(2)
Considering the delivery time window requirements of semitrailers, this paper establishes a 0-1 integer programming model for tractor scheduling optimization, aiming at the configuration cost, operation cost, and waiting cost of tractors(3)
An improved multi ant colony algorithm with a parallel search mechanism is proposed, which improves the applicability of the proposed optimization method to large-scale problems(4)
Through experiments on actual examples from Anji Logistics Enterprise in Chengdu, the effectiveness of the algorithm in generating the results of the ratio of tractors to semitrailers is proven. By comparison with the traditional method, the superiority of the optimization method is provenThe rest of this article is arranged as follows: The second section reviews the relevant literature. The third section describes this problem formally. In the fourth section, the mathematical optimization model of the problem is proposed, and in the fifth section, the improved ant search algorithm is designed. Section6 gives the calculation results of a practical case. Finally, conclusions and future work are given in Section 7.


## 2. Literature Review

Drop and pull transportation scheduling, a vehicle routing problem (VRP), which is generally defined as a complex NP hard problem by academia, is more complicated than the general vehicle routing problem because of the trailer transportation characteristics. In the truck and trailer routing problem (TTRP), the transport vehicle can be in the form of a single truck or a truck towing a trailer (this form is called a truck and trailer combination) [1].Semet [2] put forward the application of trucks with full trailers in practice earlier. Gerdessen [3] defined the routing problem of trucks with full trailers as vehicle scheduling problems with trailers. In 2002, Chao [4] first defined the scheduling problem of truck and trailer combination as the truck and trailer routing problem. Hall [5] proposed the vehicle circuit, that is, the tractor can drop one or more trailers at each node or hang one or more trailers, and developed a route cargo control strategy to determine the release plan of the tractor. Scheuerer [6] pointed out that in addition to the vehicle route, the decision point for the TTRP problem also includes the best trailer stop node and the number of times the trailer is dropped. Tan et al. [7] studied the vehicle routing problem with random demand and considered constraints such as the time window and transportation equipment capacity. The optimization objectives included mileage and driver compensation. Caramia [8, 9] studied the characteristics of the Italian farm raw milk collection problem, constructed the TTRP model, and then developed a two-stage mathematical planning method for solving the problem. Drexl [10] developed a branch pricing algorithm to solve the TTRP problem and designed a TTRP solver based on the branch cutting method. Batsyn et al. [11] studied the drop and pull transportation path problem based on batch delivery and considered the soft and hard time window constraints in the model. Li et al. [12] studied the problem of drop and pull transportation with a time window. The objective function of their research was to minimize the carbon dioxide emissions during transportation.In some specific drop and pull transportation mode scenarios, some scholars have also conducted relevant research on its characteristics. In the multimodal transport mode, Caris et al. [13] studied the problem of combined pick-up and delivery of a full load of goods with a time window in the application scenario of land and water transport. Braekers et al. [14] studied the problem of drop and pull transportation between inland areas and ports under the condition of a full load of vehicles and established a mathematical programming model to optimize the number and mileage of tractors. Zhang et al. [15] studied the multimodal transportation tractor scheduling problem under the condition of dynamic transportation tasks. Gu et al. [16] studied the tractor scheduling problem between the port and the hinterland and established a dual-objective model with the least number of tractors and the shortest mileage. You [17] studied the problem of container coupling transportation with multiple trailers. In the transportation mode of highway trunk lines, Hall [5] studied the path optimization of a closed tractor, considering the transportation situation in which one tractor can tow multiple trailers. Li [18] studied the route optimization problem of multiple to multiple networks of highway trunk transportation and took the minimum greenhouse gas emissions per kilometer as the objective function to find the lowest emission scheme. Yang [19] studied the tractor path optimization problem in the mixed case of hub and spoke hitch and network hitch and established a model including the time when the tractor arrived at the operation point. Belenguer [20] established an integer programming model for tractor path optimization problems with a single yard and multiple operation points. Yang et al. [21] studied the optimization of tractor routes based on the organization mode of hub and spoke drop and hitch transportation.Drop and pull transportation is affected by various factors such as transportation costs, policy factors, technical conditions, and transportation infrastructure. Most scholars at home and abroad use a combination of qualitative analysis and quantitative analysis to study it. Baldacci [22] considered the impact of multiple site types on the TTRP problem. Wy et al. [23] considered complex constraints in the TTRP problem including multiple disposal facilities, multiple container storage yards, different time windows for customer demands and facilities, various types and sizes of containers, and the lunch break of tractor drivers. Ulrich et al. [24] analyzed the drop and pull transport with time-limited and proposed that time is a key factor affecting the efficiency of drop and pull transport. Huang [25] concluded that the external influencing factors of drop and pull transportation are high-grade highway network, economic development level, and economic structure. Yang [26] proposed that the factors affecting drop and pull transportation are the scale of enterprise operation, laws and regulations, and logistics resources. Li [27] pointed out that the prominent problems restricting the development of drop and pull transportation include policy, technology, facilities and equipment, and safety risk management. Zhao et al. [28] believe that the policy environment and the safety technology level of drop and pull vehicles are the factors that have a greater impact on the safety level of the drop and pull transportation system. Wu [29] analyzed the factors affecting the development of drop and pull transportation from four aspects: politics, law, economy, social culture, and technology. Sun [30] believes that the choice of the operation mode of drop and pull transportation is affected by factors such as the type of goods, the volume of freight, the time of the tractor’s arrival at the port, the number of tractors owned by the enterprise, the towing fee, and the traffic or weather conditions.With regard to the NP hard characteristics of the TTRP (truck and trainer routing problem), scholars at home and abroad mostly use heuristic optimization algorithms to solve it. Villegas [31, 32] combines the hybrid heuristic algorithm based on a greedy random adaptive search program, variable neighborhood search strategy, and path reconnection operation to improve the quality of the solution. Drexl developed the branch and bound algorithm and designed the TTRP solver based on the branch and cut method [33]. In subsequent research, he proposed two planning models based on arc variables and designed the branch and cut algorithm to solve them [34]. Hu [35] designed a hybrid evolutionary algorithm based on 2-opt to solve TTRP problems. Wang [36] developed an adaptive bat algorithm to solve TTRP problems and designed five neighborhood search structures in the local search link. In addition, other scholars have designed greedy algorithms [11], genetic algorithms [7], and simulated annealing algorithms [14, 19, 37, 38] to solve TTRP problems. Relatively speaking, there is little effort to solve the problem of matching the number of tractors and semitrailers in the drop and pull transportation system. Fan [39] gives the formula for calculating the number of tractors on a single drop and pull transportation line by analyzing the time division in the process of drop and pull transportation. Cai [40], aiming at the problem of product oil dump and hitch transportation, based on the principle of queuing theory, built an optimal quantity allocation model of dump and hitch vehicles. Zhu [41] introduced the birth and death model to simulate the process of trailer assembly and dispersion in trailer dropping transportation and studied the number allocation of turnover trailers in a single station. Wang et al. [42] simulated a reasonable proportion of tractors and semitrailers in the process of coupling on the Flexsim simulation platform. In summary, most of the existing research on tractor scheduling is concentrated, and most of the research focuses on the definition of the concept of drop and pull transportation, the analysis of the influencing factors of drop and pull transportation, and the application practice of drop and pull transportation while ignoring the research on the number configuration of tractors and semitrailers from the perspective of scheduling optimization. As mentioned above, these omissions will lead to low efficiency and excessive configuration of tractors.


## 3. Problem Description

The drop and pull transportation system mainly includes two types of nodes: the drop and pull center of the tractor and the customer site. The drop and pull center of the tractor is mainly used for the parking and maintenance of tractors. The customer site is the starting point and ending point of semitrailer transportation. Figure2 is a schematic diagram of the network G=V,A′∪Λ for drop and pull transport of tractors with semitrailers. Assuming that there is a semitrailer that has been loaded at customer site A and needs to be sent to customer site B, then a tractor is assigned to customer site A; after hooking up the semitrailer and towing it to customer site B, then the semitrailer will stay at customer site B for unloading. If there is a semitrailer at customer site B that has been loaded and needs to be sent to another customer site (including customer site A), the semitrailer will be connected to this tractor to go to its destination; otherwise, the tractor will leave alone.Figure 2
The network of tractor and semitrailer transportation structures.There are one or more drop and pull centers in the physical network of drop and pull transport, which store and maintain vehicle resources (mainly tractors). Simultaneously, there are multiple customer sites with similar functions. There are semitrailers (semitrailers that have finished loading or are in the process of loading) waiting to be transported at these customer sites. The basic operation process of the network drop and pull transport is as follows: In the decision period (usually one day), the tractors start from the drop and pull centers, pull all the trailers to be transported in the system from the starting point (point O) to their destination (point D), and finally return to the drop and pull center, as shown in Figure2.The difference between this problem and the traditional vehicle routing optimization problem is that each station may be the starting point and destination of semitrailer transportation and there may be multiple different arrival stations (i.e., OD destinations) at each departure station. For each OD destination, due to the different freight volumes, the number of semitrailers to be sent is also different. Therefore, during the operation of the tractor between the customer stations, it may be in full load (coupled with a semitrailer) or no-load state (not coupled with a semitrailer). To describe this problem in a mathematical way, a virtual spatiotemporal directed graphG=V,A′∪Λ is proposed to describe the demand of drop and pull transportation based on the existing physical network of drop and pull transportation, as shown in Figure 3, where the node represents the coupling center and the customer site. Each dotted line between the customer sites represents the transportation demand of semitrailers between the two points, where the direction of the dotted line represents the transportation direction of semitrailers to be delivered and the number of dotted lines between the customer sites represents the number of semitrailers to be transported between the two points.Figure 3
The virtual network for drop and pull transportation demand.According to the virtual space-time directed graphG=V,A′∪Λ of the trailer dropping transportation demand in Figure 3, a feasible tractor operation path scheme (without considering the semitrailer time window constraint) is shown in Figure 4 and Table 1. All tractors start from the coupling center and return to the coupling center after completing the transportation of semitrailers with different destinations according to the established coupling scheduling plan.Figure 4
Schematic diagram of the tractor running path.Table 1
Tractor running path.
Tractor numberPerformance tasksTravel sites11-5-80-1-2-3-4-023-2-60-5-1-2-3-0310-15-130-5-6-7-8-4-0411-40-6-5-1-0512-9-70-8-4-3-2-0616-140-8-7-6-0


## 4. Model Formulation

### 4.1. Notations

#### 4.1.1. Assumption

The following assumptions are made throughout this article, and natations used in the paper is shown in Table2:
(1)
The scheduling of empty semitrailers is not considered(2)
The measurement unit of the freight demand on the customer sites is the carrying capacity of one semitrailer(3)
Transportation demand can exist between any 2 customer sites(4)
Each OD destination has only one time window. If a tractor arrives before the time window, it needs to wait until the time window opens before towing another semitrailer to leave; if the tractor arrives after the time window, it can only drop the semitrailer and drive directly to the next site by itself(5)
The tractor and trailer participating in the drop and pull transportation task are of the same model, the fuel consumption and running speed are considered according to the same numerical indicators, and the tractor and the trailer vehicle can be cross-linked(6)
The drop and pull transportation process is implemented smoothly, without considering the impacts of traffic accidents and road congestion(7)
The operation time of connecting and dropping the trailer at the customer site can be ignored in the overall transportation timeTable 2
Notations used in the paper.
General subscripts and setsi,jIndex of stationskNumber of tractorsmNumber of trailers to be transportedParametersS=siCollection of sites in drop and pull transportation operations;s0Drop and pull centersS/s0Customer sitesE=i,ji,j∈SCollection of interstation linesD=diji,j∈SnMatrix of distance between stationsdijDistance between sitei and site jtikTime point when tractork arrives at customer site iQ=qijmA set of tasks that need to be transported between the sitesqijmTaskm,the transportation volume from start pointi to end point jT=t1m,t2mm=1,2,⋯,MTime window of each taskt1mLower limit of the time window, which means the start time of taskmt2mUpper limit of the time window, which means the end time of taskms1mDeparture station of taskms2mArrival station of taskmwmkWaiting time for tractork to perform task mR=rkPath set of tractors, that is, all the paths that each tractor takes in the execution of the all-day taskv1The average speed of the vehicle under load (km/h)v2The average speed of the vehicle under unload (km/h)c0Purchase cost of tractor (yuan/vehicle)c1Driving cost of tractor under load (yuan/km)c2Driving cost of tractor not under load (yuan/km)c3Waiting costs for tractor to arrive at task site early (yuan/h)Variablesxi,jkWhether tractork is driving on road section i,jwith load; if yes, the value is 1; if not, the value is 0yi,jkWhether tractork is driving on road section i,j with no load, if yes, the value is 1; if not, the value is 0zmkWhether tractork completes task m; if yes, the value is 1; if not, the value is 0


### 4.2. Model

When arranging a tractor to transport a semitrailer, the operator seeks a scheduling scheme that minimizes operating costs, where the operating cost includes the acquisition cost of the tractor, the operating cost of the tractor, and the waiting cost of the tractor. The fixed purchase cost of vehicles is determined by the number of tractor vehicles and the unit purchase cost. On the premise of completing all semitrailer distribution tasks according to the requirements of the time window, different tractor route schemes often lead to different configuration numbers of tractors. The vehicle operating cost is determined by the sum of the path distance traveled by all towing vehicles and the cost per unit operating distance. The comprehensive waiting cost of vehicles is determined by the waiting task time of all tractor vehicles and the cost of unit waiting time. The optimal model of the tractor routing problem is shown in (1)–(12):
(1)minZ1=c0K,(2)minZ2=∑k=1K∑m∈Mc1wmk+∑k=1K∑i,j∈Sndijc2xi,jk+c3yi,jk,(3)subjectto∑k=1Kzmk=qijm;∀i,j∈Sn,∀m∈M,(4)∑k=1Kxs1m,s2mk=1;∀m∈M,(5)∑i∈Sn/s0x0,ik=∑i∈Sn/s0xi,0k=0;∀k∈K,(6)∑i∈Sn/s0y0,ik=∑i∈Sn/s0yi,0k=1;∀k∈K,(7)∑i,j∈Sn/s0xi,jk+yi,jk≤1;∀k∈K,(8)M⋅zmk≥wmk;∀k∈K,∀m∈M,(9)wmk=ts2m−1k−dijxs2m−1,s1mkv1+ys2m−1,s1mkv2;∀k∈K,∀m∈M,(10)ts1mk+ws1mk+M1−∑j∈Snxi,jk≥tm1;∀k∈K;m∈M,(11)ts1mk+ws1mk+ts1m,s2m−M1−∑j∈Snxi,jk≤tm2;∀k∈K;m∈M,(12)xi,jk,yi,jk,zmk∈0,1;∀i,j∈Sn;k∈K;m∈M.Objective function (1) minimizes the acquisition cost of the tractors, and objective function (2) minimizes the cost of vehicle waiting time and vehicle operating mileage produced by the tractors. To solve the model, a weight coefficient (ω1,ω2) is introduced on these two components. Then, by adding functions, the dual objective function is transformed into a single objective function. The weight value reflects the decision-maker’s preference for minimizing the total acquisition cost and total operating cost of the tractor. Since the above two play an important role in drop and pull transportation scheduling, this paper regards these two components as the same expected level, so we set ω1=ω2=1.Constraint (3) requires that all semitrailer transport tasks be completed. Constraint (4) ensures that the transport task between each customer site must be serviced only one time by a tractor. Constraints (5) to (7) are the path closure constraints of the tractor, which means that the tractor departs from its storage base to the customer site and then returns to the drop and pull center of the tractor after the drop and pull operation between the customer sites. Constraints (8) to (9) limit the waiting time for the tractor to transport each task. Constraints (10) to (11) are time window constraints, which refer to whether the time when the tractor arrives at the departure station and the final station is within the time window of the task. This paper stipulates that when the tractor arrives at the departure station earlier than the earliest time window, there will be a waiting penalty cost, and the late arrival will not incur penalty cost, but it is required that the tractor arrives at the final station not later than the latest time of the time window. Constraints (12) are decision variable constraints.


## 4.1. Notations

### 4.1.1. Assumption

The following assumptions are made throughout this article, and natations used in the paper is shown in Table2:
(1)
The scheduling of empty semitrailers is not considered(2)
The measurement unit of the freight demand on the customer sites is the carrying capacity of one semitrailer(3)
Transportation demand can exist between any 2 customer sites(4)
Each OD destination has only one time window. If a tractor arrives before the time window, it needs to wait until the time window opens before towing another semitrailer to leave; if the tractor arrives after the time window, it can only drop the semitrailer and drive directly to the next site by itself(5)
The tractor and trailer participating in the drop and pull transportation task are of the same model, the fuel consumption and running speed are considered according to the same numerical indicators, and the tractor and the trailer vehicle can be cross-linked(6)
The drop and pull transportation process is implemented smoothly, without considering the impacts of traffic accidents and road congestion(7)
The operation time of connecting and dropping the trailer at the customer site can be ignored in the overall transportation timeTable 2
Notations used in the paper.
General subscripts and setsi,jIndex of stationskNumber of tractorsmNumber of trailers to be transportedParametersS=siCollection of sites in drop and pull transportation operations;s0Drop and pull centersS/s0Customer sitesE=i,ji,j∈SCollection of interstation linesD=diji,j∈SnMatrix of distance between stationsdijDistance between sitei and site jtikTime point when tractork arrives at customer site iQ=qijmA set of tasks that need to be transported between the sitesqijmTaskm,the transportation volume from start pointi to end point jT=t1m,t2mm=1,2,⋯,MTime window of each taskt1mLower limit of the time window, which means the start time of taskmt2mUpper limit of the time window, which means the end time of taskms1mDeparture station of taskms2mArrival station of taskmwmkWaiting time for tractork to perform task mR=rkPath set of tractors, that is, all the paths that each tractor takes in the execution of the all-day taskv1The average speed of the vehicle under load (km/h)v2The average speed of the vehicle under unload (km/h)c0Purchase cost of tractor (yuan/vehicle)c1Driving cost of tractor under load (yuan/km)c2Driving cost of tractor not under load (yuan/km)c3Waiting costs for tractor to arrive at task site early (yuan/h)Variablesxi,jkWhether tractork is driving on road section i,jwith load; if yes, the value is 1; if not, the value is 0yi,jkWhether tractork is driving on road section i,j with no load, if yes, the value is 1; if not, the value is 0zmkWhether tractork completes task m; if yes, the value is 1; if not, the value is 0


## 4.1.1. Assumption

The following assumptions are made throughout this article, and natations used in the paper is shown in Table2:
(1)
The scheduling of empty semitrailers is not considered(2)
The measurement unit of the freight demand on the customer sites is the carrying capacity of one semitrailer(3)
Transportation demand can exist between any 2 customer sites(4)
Each OD destination has only one time window. If a tractor arrives before the time window, it needs to wait until the time window opens before towing another semitrailer to leave; if the tractor arrives after the time window, it can only drop the semitrailer and drive directly to the next site by itself(5)
The tractor and trailer participating in the drop and pull transportation task are of the same model, the fuel consumption and running speed are considered according to the same numerical indicators, and the tractor and the trailer vehicle can be cross-linked(6)
The drop and pull transportation process is implemented smoothly, without considering the impacts of traffic accidents and road congestion(7)
The operation time of connecting and dropping the trailer at the customer site can be ignored in the overall transportation timeTable 2
Notations used in the paper.
General subscripts and setsi,jIndex of stationskNumber of tractorsmNumber of trailers to be transportedParametersS=siCollection of sites in drop and pull transportation operations;s0Drop and pull centersS/s0Customer sitesE=i,ji,j∈SCollection of interstation linesD=diji,j∈SnMatrix of distance between stationsdijDistance between sitei and site jtikTime point when tractork arrives at customer site iQ=qijmA set of tasks that need to be transported between the sitesqijmTaskm,the transportation volume from start pointi to end point jT=t1m,t2mm=1,2,⋯,MTime window of each taskt1mLower limit of the time window, which means the start time of taskmt2mUpper limit of the time window, which means the end time of taskms1mDeparture station of taskms2mArrival station of taskmwmkWaiting time for tractork to perform task mR=rkPath set of tractors, that is, all the paths that each tractor takes in the execution of the all-day taskv1The average speed of the vehicle under load (km/h)v2The average speed of the vehicle under unload (km/h)c0Purchase cost of tractor (yuan/vehicle)c1Driving cost of tractor under load (yuan/km)c2Driving cost of tractor not under load (yuan/km)c3Waiting costs for tractor to arrive at task site early (yuan/h)Variablesxi,jkWhether tractork is driving on road section i,jwith load; if yes, the value is 1; if not, the value is 0yi,jkWhether tractork is driving on road section i,j with no load, if yes, the value is 1; if not, the value is 0zmkWhether tractork completes task m; if yes, the value is 1; if not, the value is 0


## 4.2. Model

When arranging a tractor to transport a semitrailer, the operator seeks a scheduling scheme that minimizes operating costs, where the operating cost includes the acquisition cost of the tractor, the operating cost of the tractor, and the waiting cost of the tractor. The fixed purchase cost of vehicles is determined by the number of tractor vehicles and the unit purchase cost. On the premise of completing all semitrailer distribution tasks according to the requirements of the time window, different tractor route schemes often lead to different configuration numbers of tractors. The vehicle operating cost is determined by the sum of the path distance traveled by all towing vehicles and the cost per unit operating distance. The comprehensive waiting cost of vehicles is determined by the waiting task time of all tractor vehicles and the cost of unit waiting time. The optimal model of the tractor routing problem is shown in (1)–(12):
(1)minZ1=c0K,(2)minZ2=∑k=1K∑m∈Mc1wmk+∑k=1K∑i,j∈Sndijc2xi,jk+c3yi,jk,(3)subjectto∑k=1Kzmk=qijm;∀i,j∈Sn,∀m∈M,(4)∑k=1Kxs1m,s2mk=1;∀m∈M,(5)∑i∈Sn/s0x0,ik=∑i∈Sn/s0xi,0k=0;∀k∈K,(6)∑i∈Sn/s0y0,ik=∑i∈Sn/s0yi,0k=1;∀k∈K,(7)∑i,j∈Sn/s0xi,jk+yi,jk≤1;∀k∈K,(8)M⋅zmk≥wmk;∀k∈K,∀m∈M,(9)wmk=ts2m−1k−dijxs2m−1,s1mkv1+ys2m−1,s1mkv2;∀k∈K,∀m∈M,(10)ts1mk+ws1mk+M1−∑j∈Snxi,jk≥tm1;∀k∈K;m∈M,(11)ts1mk+ws1mk+ts1m,s2m−M1−∑j∈Snxi,jk≤tm2;∀k∈K;m∈M,(12)xi,jk,yi,jk,zmk∈0,1;∀i,j∈Sn;k∈K;m∈M.Objective function (1) minimizes the acquisition cost of the tractors, and objective function (2) minimizes the cost of vehicle waiting time and vehicle operating mileage produced by the tractors. To solve the model, a weight coefficient (ω1,ω2) is introduced on these two components. Then, by adding functions, the dual objective function is transformed into a single objective function. The weight value reflects the decision-maker’s preference for minimizing the total acquisition cost and total operating cost of the tractor. Since the above two play an important role in drop and pull transportation scheduling, this paper regards these two components as the same expected level, so we set ω1=ω2=1.Constraint (3) requires that all semitrailer transport tasks be completed. Constraint (4) ensures that the transport task between each customer site must be serviced only one time by a tractor. Constraints (5) to (7) are the path closure constraints of the tractor, which means that the tractor departs from its storage base to the customer site and then returns to the drop and pull center of the tractor after the drop and pull operation between the customer sites. Constraints (8) to (9) limit the waiting time for the tractor to transport each task. Constraints (10) to (11) are time window constraints, which refer to whether the time when the tractor arrives at the departure station and the final station is within the time window of the task. This paper stipulates that when the tractor arrives at the departure station earlier than the earliest time window, there will be a waiting penalty cost, and the late arrival will not incur penalty cost, but it is required that the tractor arrives at the final station not later than the latest time of the time window. Constraints (12) are decision variable constraints.


## 5. Solution Algorithm

The application of the tractor scheduling model with a time window in practical operation easily becomes very large in scale, especially for the vehicle scheduling problem widely considered NP-hard. Therefore, the tractor scheduling model proposed in Section4 is plagued by dimensional problems due to the rapid increase in the number of Formulas (1) to (12). Therefore, a widely used heuristic algorithm, the ant colony optimization algorithm (ACS), is used to find a good solution within a reasonable calculation time.The core idea of the basic ant colony algorithm is to use the ant walking path to represent the feasible solution of the problem to be optimized. All paths of the whole ant colony constitute the solution space of the problem to be optimized. Ants with shorter paths release more pheromones, so the accumulated pheromone concentration increases faster, so this optimal path finally becomes the optimal solution of the problem [43]. However, the movement of ant individuals is random, which usually makes the algorithm search evolution slow and even stagnant. Considering the inherent parallelism of the ant colony algorithm, we propose an improved multi ant colony algorithm combined with a parallel search mechanism: At the initial moment, the ant colony is divided into groups, each group releases the pheromone of its own group, and a rejection technique is used to prevent ant groups of different groups from choosing the same path so that ant agents can search more paths and improve the search space as much as possible. (I) When the ant is at the decision point without pheromones, it will make a random choice, which is similar to the basic ant colony algorithm; (II) when the path contains pheromones from the group, ants will choose the path with a higher probability; and (III) when the path contains pheromones from other groups, the ants will choose the path with a low probability due to the effect of exclusion. In this way, ants can be prevented from stagnating on a suboptimal solution due to random selection. Using multi ant colony search and indirect communication through pheromones, it has implicit parallelism and adaptability.


### 5.1. Solution Space Structure

One of the key problems of the ant colony algorithm is how to map the problem to be solved into a solution structure graph and obtain a feasible solution of the problem through the route of artificial ants from the starting point to the end point on the graph. According to the characteristics of the tractor routing model of drop and pull transport, the scheme design of the solution space is shown in Figure5.Figure 5
The solution structure diagram of the tractor routing problem.In the figure,qi represents the task i in the drop and pull task set Q; the solid line eij indicates that the tractor completes a task qi and then starts another task qj, and its weight is the cost of the tractor traveling from the final site si2 to the originating station sj1. The dotted line eij′ is an auxiliary edge, which is used to connect qi and qj, and its weight is M to ensure that a feasible solution can be found in each iteration. The existence of multiple s0 in the figure means that when a tractor completes a task, it cannot go to the next customer site due to the constraints of the time window, and it can return to the drop and pull center s0. Additionally, the number of tractors that can be used is increased by 1.The process of ants constructing solutions on the graph is the process of ants starting from the tractor centers0, finishing all tasks qi and then returning to s0. The route of the ants constitutes a feasible solution to the application plan of the arrival and departure line. The thick solid line in Figure 6 is the walking route of the ants during the deconstruction process, representing a feasible solution F.Therefore, the feasible solution F of the optimal ratio of tractors and trailers can be expressed as the set of real edges traversed by ants. For example, route s0→q2→→q8→q6→s0 means that the first tractor starts from tractor center s0; completes tasks q2, q5, q8, and q6 successively; and then returns to s0.Figure 6
Convergence curve of the ant colony algorithm.When ants move from taskqi to task qj in Figure 6, they need to satisfy model constraints (3) to (11). Nik is the candidate task set of ant k on node qi, which is obtained by the operation of the continuous task 1,2,⋯,i−1selected by ant k, constraints (3) to (11), and the cost matrix C. When Nik=∅, it means that after starting from task qi, there is no successive task that satisfies the constraints; then, Nik=s0, through Nik can ensure that the construction solution satisfies the constraints.


### 5.2. Attraction Factor and Exclusion Factor

Aks refers to the agent of the s-th ant in the k-th population, and the ants in this population release the same type of pheromone, which is identified by the color number s. Different populations release different types of pheromones. At present, the ant is located in city i. In its neighborhood Ni, it selects the next moving city j according to some probability and will make a choice according to the joint action of pheromone concentration attraction of its own type and pheromone concentration repulsion of other population types on the path.


#### 5.2.1. Attraction Factor

ξijk is the attraction factor of the s-type pheromone of the s-type ant that is currently located in city i and selects the next city j in its neighborhood Ni. It is defined by the following equation:
(13)ξijs=τijs/∑h∈Niτihs,where τijs is the concentration of the s-th pheromone on edge i,j.


#### 5.2.2. Exclusion Factor

ζijs is the exclusion factor of the s-type pheromone of the next city j selected in neighborhood Ni of the ant of the s population currently located in city i. It is defined by the following equation:
(14)ζijs=∑k≠sτijk/∑h∈Niτihs.


### 5.3. Node Selection Strategy Design

This paper designs improved ant colony transfer rules: (1) multiple ant colonies are used to perform search tasks in parallel, and ants of different populations release different types of pheromones. (2) Pheromones released by ants are attractive to ants of this population; they can repel ants from other populations. (3) The interaction of attraction and repulsion, together with heuristic information, determines the transfer selection probability of ants.When thek-th ant in population s is at task node qi, a decision rule of probability pijsk is used to select the next task node qj.
(15)pijsk=α⋅τij⋅κ+β⋅ηij∑j∈Nikα⋅τij⋅κ+β⋅ηijj∈Nik0j∉Nik.In the formula,ηij is the heuristic information, which refers to the heuristic expectation degree of task node qj following task node qi. This paper stipulates that ηij=1/cij, where cij is the cost consumption between task qi and task qj performed by the tractor, including the operation cost and waiting time cost of running the tractor, and 0≤α,β≤1 are used to represent the role of pheromone τij and heuristic information ηij in constructing the solution. In the initial stage of the search, the pheromone is used as the initial value and does not have any guiding effect on the behavior of the ants, which will cause the algorithm to construct a path of very low quality. The main function of heuristic information is to avoid this situation, which makes the ants tend to construct a good path from the beginning. When Nik≠∅, ant k selects the next task node at task node qi according to probability pijkt, similar to roulette in the evolutionary algorithm. When Nik=∅, that is, when task qi is completed, the tractor selects the tractor center s0 with a probability of pi0kt=1.


### 5.4. Pheromone Rule Design

Pheromoneτij refers to the expectation from task qi to task qj. The better the performance of the solution searched by the ant, the more concentrated the pheromone left on the path it passes. Therefore, in the optimal ratio of tractor and trailers, the value of the pheromone should be inversely proportional to the value of the objective function.


#### 5.4.1. Pheromone Initialization

To expand the search range of the ants in the solution space at the beginning of the iteration, the pheromone on all the solid lines in the deconstruction graph is initialized toτ0, and all the dotted lines in the graph are auxiliary edges and do not play a decision-making role, so there are no pheromones on them.


#### 5.4.2. Principle of Pheromone Update

The pheromone update strategy is one of the key steps of the ant colony algorithm. If the information is updated too quickly, the algorithm will fall into a local optimum or even stagnate. If the information is updated too slowly, the convergence speed will be slow, and the optimal route cannot be searched. The pheromone update principle adopted by the algorithm is that after each iteration, all ants update the pheromone according to the quality of the solution searched by them, as shown in Formula (14), and local pheromone updates are not continuously performed during the construction of the solution.
(16)τijt+1=ρτijt+Δτij.In the formula,ρ is the volatility coefficient of pheromone, ρ<1; t is the current iteration number; and Δτij is the pheromone increment after the current iteration, with a calculation formula as follows:
(17)Δτij=Z∗/Zeij∈S0eij∉S0.


### 5.5. ACO Algorithm

The steps of the ACO algorithm to solve the model are as follows:Step 1 Set the parameters of the ant colony algorithmStep 2 Generate the initial solutions of all subgroups, and set the initial pheromone value and current iteration times for each edge of each subgroupn⟵1Step 3 Place all the ants in the center of the tractor. Each ant randomly selects the next node according to the law of Formula (15) and obtains its own pathStep 4 The pheromone on each path is updated according to the improved global pheromone Formulas (16) and (17)Step 5 For the current number of iterationsn⟵n+1, judge whether n reaches the maximum number of iterations. If yes, go to Step 5; otherwise, go to Step 2Step 6 Output the current optimal solution


## 5.1. Solution Space Structure

One of the key problems of the ant colony algorithm is how to map the problem to be solved into a solution structure graph and obtain a feasible solution of the problem through the route of artificial ants from the starting point to the end point on the graph. According to the characteristics of the tractor routing model of drop and pull transport, the scheme design of the solution space is shown in Figure5.Figure 5
The solution structure diagram of the tractor routing problem.In the figure,qi represents the task i in the drop and pull task set Q; the solid line eij indicates that the tractor completes a task qi and then starts another task qj, and its weight is the cost of the tractor traveling from the final site si2 to the originating station sj1. The dotted line eij′ is an auxiliary edge, which is used to connect qi and qj, and its weight is M to ensure that a feasible solution can be found in each iteration. The existence of multiple s0 in the figure means that when a tractor completes a task, it cannot go to the next customer site due to the constraints of the time window, and it can return to the drop and pull center s0. Additionally, the number of tractors that can be used is increased by 1.The process of ants constructing solutions on the graph is the process of ants starting from the tractor centers0, finishing all tasks qi and then returning to s0. The route of the ants constitutes a feasible solution to the application plan of the arrival and departure line. The thick solid line in Figure 6 is the walking route of the ants during the deconstruction process, representing a feasible solution F.Therefore, the feasible solution F of the optimal ratio of tractors and trailers can be expressed as the set of real edges traversed by ants. For example, route s0→q2→→q8→q6→s0 means that the first tractor starts from tractor center s0; completes tasks q2, q5, q8, and q6 successively; and then returns to s0.Figure 6
Convergence curve of the ant colony algorithm.When ants move from taskqi to task qj in Figure 6, they need to satisfy model constraints (3) to (11). Nik is the candidate task set of ant k on node qi, which is obtained by the operation of the continuous task 1,2,⋯,i−1selected by ant k, constraints (3) to (11), and the cost matrix C. When Nik=∅, it means that after starting from task qi, there is no successive task that satisfies the constraints; then, Nik=s0, through Nik can ensure that the construction solution satisfies the constraints.


## 5.2. Attraction Factor and Exclusion Factor

Aks refers to the agent of the s-th ant in the k-th population, and the ants in this population release the same type of pheromone, which is identified by the color number s. Different populations release different types of pheromones. At present, the ant is located in city i. In its neighborhood Ni, it selects the next moving city j according to some probability and will make a choice according to the joint action of pheromone concentration attraction of its own type and pheromone concentration repulsion of other population types on the path.


### 5.2.1. Attraction Factor

ξijk is the attraction factor of the s-type pheromone of the s-type ant that is currently located in city i and selects the next city j in its neighborhood Ni. It is defined by the following equation:
(13)ξijs=τijs/∑h∈Niτihs,where τijs is the concentration of the s-th pheromone on edge i,j.


### 5.2.2. Exclusion Factor

ζijs is the exclusion factor of the s-type pheromone of the next city j selected in neighborhood Ni of the ant of the s population currently located in city i. It is defined by the following equation:
(14)ζijs=∑k≠sτijk/∑h∈Niτihs.


## 5.2.1. Attraction Factor

ξijk is the attraction factor of the s-type pheromone of the s-type ant that is currently located in city i and selects the next city j in its neighborhood Ni. It is defined by the following equation:
(13)ξijs=τijs/∑h∈Niτihs,where τijs is the concentration of the s-th pheromone on edge i,j.


## 5.2.2. Exclusion Factor

ζijs is the exclusion factor of the s-type pheromone of the next city j selected in neighborhood Ni of the ant of the s population currently located in city i. It is defined by the following equation:
(14)ζijs=∑k≠sτijk/∑h∈Niτihs.


## 5.3. Node Selection Strategy Design

This paper designs improved ant colony transfer rules: (1) multiple ant colonies are used to perform search tasks in parallel, and ants of different populations release different types of pheromones. (2) Pheromones released by ants are attractive to ants of this population; they can repel ants from other populations. (3) The interaction of attraction and repulsion, together with heuristic information, determines the transfer selection probability of ants.When thek-th ant in population s is at task node qi, a decision rule of probability pijsk is used to select the next task node qj.
(15)pijsk=α⋅τij⋅κ+β⋅ηij∑j∈Nikα⋅τij⋅κ+β⋅ηijj∈Nik0j∉Nik.In the formula,ηij is the heuristic information, which refers to the heuristic expectation degree of task node qj following task node qi. This paper stipulates that ηij=1/cij, where cij is the cost consumption between task qi and task qj performed by the tractor, including the operation cost and waiting time cost of running the tractor, and 0≤α,β≤1 are used to represent the role of pheromone τij and heuristic information ηij in constructing the solution. In the initial stage of the search, the pheromone is used as the initial value and does not have any guiding effect on the behavior of the ants, which will cause the algorithm to construct a path of very low quality. The main function of heuristic information is to avoid this situation, which makes the ants tend to construct a good path from the beginning. When Nik≠∅, ant k selects the next task node at task node qi according to probability pijkt, similar to roulette in the evolutionary algorithm. When Nik=∅, that is, when task qi is completed, the tractor selects the tractor center s0 with a probability of pi0kt=1.


## 5.4. Pheromone Rule Design

Pheromoneτij refers to the expectation from task qi to task qj. The better the performance of the solution searched by the ant, the more concentrated the pheromone left on the path it passes. Therefore, in the optimal ratio of tractor and trailers, the value of the pheromone should be inversely proportional to the value of the objective function.


### 5.4.1. Pheromone Initialization

To expand the search range of the ants in the solution space at the beginning of the iteration, the pheromone on all the solid lines in the deconstruction graph is initialized toτ0, and all the dotted lines in the graph are auxiliary edges and do not play a decision-making role, so there are no pheromones on them.


### 5.4.2. Principle of Pheromone Update

The pheromone update strategy is one of the key steps of the ant colony algorithm. If the information is updated too quickly, the algorithm will fall into a local optimum or even stagnate. If the information is updated too slowly, the convergence speed will be slow, and the optimal route cannot be searched. The pheromone update principle adopted by the algorithm is that after each iteration, all ants update the pheromone according to the quality of the solution searched by them, as shown in Formula (14), and local pheromone updates are not continuously performed during the construction of the solution.
(16)τijt+1=ρτijt+Δτij.In the formula,ρ is the volatility coefficient of pheromone, ρ<1; t is the current iteration number; and Δτij is the pheromone increment after the current iteration, with a calculation formula as follows:
(17)Δτij=Z∗/Zeij∈S0eij∉S0.


## 5.4.1. Pheromone Initialization

To expand the search range of the ants in the solution space at the beginning of the iteration, the pheromone on all the solid lines in the deconstruction graph is initialized toτ0, and all the dotted lines in the graph are auxiliary edges and do not play a decision-making role, so there are no pheromones on them.


## 5.4.2. Principle of Pheromone Update

The pheromone update strategy is one of the key steps of the ant colony algorithm. If the information is updated too quickly, the algorithm will fall into a local optimum or even stagnate. If the information is updated too slowly, the convergence speed will be slow, and the optimal route cannot be searched. The pheromone update principle adopted by the algorithm is that after each iteration, all ants update the pheromone according to the quality of the solution searched by them, as shown in Formula (14), and local pheromone updates are not continuously performed during the construction of the solution.
(16)τijt+1=ρτijt+Δτij.In the formula,ρ is the volatility coefficient of pheromone, ρ<1; t is the current iteration number; and Δτij is the pheromone increment after the current iteration, with a calculation formula as follows:
(17)Δτij=Z∗/Zeij∈S0eij∉S0.


## 5.5. ACO Algorithm

The steps of the ACO algorithm to solve the model are as follows:Step 1 Set the parameters of the ant colony algorithmStep 2 Generate the initial solutions of all subgroups, and set the initial pheromone value and current iteration times for each edge of each subgroupn⟵1Step 3 Place all the ants in the center of the tractor. Each ant randomly selects the next node according to the law of Formula (15) and obtains its own pathStep 4 The pheromone on each path is updated according to the improved global pheromone Formulas (16) and (17)Step 5 For the current number of iterationsn⟵n+1, judge whether n reaches the maximum number of iterations. If yes, go to Step 5; otherwise, go to Step 2Step 6 Output the current optimal solution


## 6. Numerical Experiments

This section presents the numerical experimental results of the instance. Part A describes actual data received from Anji Logistics Enterprise in Chengdu, Sichuan Province, China. Part B reports the computational results on real-world instances of the drop and pull transportation plan of Anji Logistics Enterprise. Part C designs a set of examples to evaluate the proposed models and algorithms based on these data and gives experimental results on artificial examples to illustrate the effectiveness of the ACO algorithm. All experiments are performed on a PC with a 3.40 GHz CPU and 16 GB RAM using MATLAB2012A.


### 6.1. Basic Experiments for an Idealized Tractor and Semitrailer System

Anji Logistics Enterprise includes 1 drop and pull center and 8 customer sites. According to the data received on one implementation day, a total of 73 drop and pull tasks (73 trailers) need to be performed, which constitute the taskQ of the drop and pull transport network.The relevant parameters are as follows: The average travel speed of the heavy-load tractor isv1=40 km/h, the no-load driving speed is v2=60 km/h, the daily fixed cost is c0=500 RMB/unit, the heavy-load driving cost of the tractor is c1=2.4 RMB/km, the no-load driving cost is c2=2.0 RMB/km, and the waiting cost is c3=1.5 RMB/hour. The transportation distance between each node is shown in Table 3. The transportation demand of each node and the corresponding time window limit-related data refer to the transportation account of Anji Logistics Enterprise in September 2021, as shown in Tables 4 and 5, respectively.Table 3
Distance matrix between sites of drop and pull transport network (unit: km).
0123456780—6072726090108132162160—549078120102787227254—10290120102787237290102—7278426090460789072—543658785901081207854—13842726108901024236138—78487132727860484278—42816278729078724842—Table 4
Transportation demand between sites of drop and pull transportation network (unit: vehicle).
123456781—020302321—1312313—2102042—3212531—2236212—237213—281132—Table 5
Time window for drop and pull transport operations (unit: hour).
123456781——[12, 17]—[13, 17]—[11, 15][12, 17]2[9, 15]—[9, 12][8, 11][9, 14][8, 12][10, 15][12, 16]3—[10, 15][8, 12]—[12, 17]—4[10, 15]—[9, 12][11, 15][8, 11][10, 14]5[11, 16][10, 15]—[9, 12][10, 17][12, 18]6[10, 16][12, 16][9, 14]—[10, 15][11, 16]7[8, 12][12, 15][10, 16]—[8, 12]8[11, 16][12, 18][12, 16][9, 15]—


### 6.2. Experiments for Anji Logistics Enterprise in Chengdu

We use the MATLAB software algorithm, where the parameters of the ACO algorithm are set as follows: the number of antsm=22, the pheromone importance parameter alpha=1, the heuristic factor importance parameter beta=4, the pheromone evaporation coefficient rho=0.2, the pheromone increase intensity coefficient Q=20, and the maximum number of iterations of the algorithm NC_max=130.It can be seen that the ant colony algorithm has good convergence in solving the proposed model and the gradually stable optimization results are shown in Figure6. The total running time of the algorithm is approximately 16.3 s, and the algorithm remains stable when the number of iterations reaches approximately 30. The total cost of the entire drop and pull system is approximately 6.83 × 104 RMB.The function values of each sub-objective are shown in Figures7–9 with the convergence of the algorithm iteration. Figure 7 shows the convergence of the number of tractors with the algorithm iteration. After the algorithm converges, the number of tractors is 22. Figure 8 shows the convergence of the total waiting time of the tractor with the algorithm iteration. After the algorithm converges, the total waiting time of the tractor is 19.8 hours. Figure 9 shows the convergence of the running mileage of the tractor with the algorithm iteration. After the algorithm converges, the running mileage of the tractor is approximately 13,270 kilometers. Judging from the curve convergence of the above three objectives, the convergence curve of the number of tractors is most similar to the convergence curve of the total cost of the drop and pull system because in the comprehensive cost of the drop and pull system, the cost of tractor purchase occupies the largest proportion.Figure 7
Convergence curve with the objective of vehicle number.Figure 8
Convergence curve with the objective of vehicle waiting time.Figure 9
Convergence curve with the objective of running mileage.Compared with the current drop and pull scheme (as shown in Tables6 and 7), the overall cost of the optimized drop and pull scheme is reduced by 15,776 RMB, which is 18.7% lower than the exiting scheme. On the premise of completing the coupling task in strict accordance with the time window limit, the number of tractors required is reduced from 51 to 22. In the exiting drop and pull scheme of the tractor, the ratio of the number of tractors to trailers is approximately 1 : 1.43, each tractor performs 1 to 2 drop and pull tasks (Figure 10), and the average travel distance of the tractor is approximately 329.1 km. In the optimized drop and pull scheme of the tractor, the ratio of the number of tractors to trailers is approximately 1 : 3.31, most tractors perform 3 to 5 drop and pull tasks (Figure 11), and the average tractor travel distance is approximately 603.2 km. The running distance of each tractor has been doubled, which greatly reduces the number of tractors equipped on the premise that all semitrailer distribution tasks are completed according to the time window requirements.Table 6
The exiting drop and pull scheme of the tractor.
Tractor numberPerformance tasks and travel sitesTractor numberPerformance tasks and travel sites17-5 (0-2-8-2-6-0)2720-2 (0-3-8-2-4-0)24-53 (0-2-6-7-5-0)2815-35 (0-3-5∗-8-0)33 (0-2-6-0)2922-26 (0-3-9-4-8-0)443 (0-6-7-0)3029 (0-5-3-0)540 (0-6-2-0)3158 (0-7-9-0)661 (0-8-5-0)3236 (0-5-9-0)751 (0-7-4-0)3319 (0-3-8-0)89-45 (0-2-9-6-8-0)3470 (0-9-4-0)972-47 (0-9-6∗-9-0)3518-66 (0-3-7-8-9-0)1030-11 (0-5-6-3-2-0)3660-1 (0-8-3-2-4-0)1141 (0-6-4-0)3762 (0-8-6-0)1254 (0-7-8)3832 (0-5-6-0)136-73 (0-2-8-9-6-0)3913 (0-3-5-0)1423-39 (0-4-5-6-2-0)4050 (0-7-3-0)1531-71 (0-5-6-9-4-0)4157 (0-7-9-0)1649 (0-7-3-0)4244 (0-6-8-0)1748-67 (0-6-9∗-2-0)4363-10 (0-8-6-2-9-0)1825-42 (0-4-6∗-7-0)4464-46 (0-8-6∗-9-0)1969 (0-9-4-0)4556-12 (0-7-9-3-4-0)2024 (0-4-5-0)4627 (0-4-8-0)2128 (0-5-3-0)4768 (0-9-3-0)2255 (0-7-8-0)4834 (0-5-7-0)2321-59 (0-3-8∗-3-0)4952-65 (0-7-5-8-9-0)2416-37 (0-3-6-5-9-0)5014-38 (0-3-5-6-2-0)258 (0-2-9-0)5133 (0-2-9-0)2617 (0-2-6-0)Vehicle informationNumber of tractors 51, number of trailers 73, rate 1 : 1.43Total cost84143Note: The symbol “∗” represents the customer site where the end point of the last task coincides with the start point of the next task.Table 7
The optimized drop and pull scheme of the tractor.
Tractor numberPerformance tasksTravel sites128-14-69-120-5-3∗-5-3-5-3-5-0259-73-22-430-8-3-9-6-9-6-9-6-0332-10-20-500-5-6-2-9-2-9-2-9-044-58-540-2-6-7-9-7-9-0571-7-600-9-4-2-8-2-8-069-720-2-9∗-6-0737-56-350-5-9-7-9-7-9-081-70-44-460-2-4-9-4-9-4-9-4-0923-18-680-4-5-3-7-3-7-01047-13-390-6-9-3-5-3-5-01153-41-3-360-7-5-6-4-6-4-6-4-01257-63-62-66-490-7-9-8-6-8-6-8-6-8-6-0138-6-240-2-9-2-8-2-8-01464-38-300-8-6∗-2-6-2-0152-400-2-4-6-2-01652-42-110-7-5-6-7-6-7-01745-21-160-6-8-3-8-3-8-01817-27-150-3-7-4-8-4-8-01961-31-51-330-8-5∗-6-5-6-5-6-02055-5-260-7-8-2-6-2-6-02148-67-34-190-6-9∗-2-9-2-9-2-02229-25-650-5-3-4-6-4-6-0Vehicle informationNumber of tractors 22, number of trailers 73, rate 1 : 3.31Total cost68367Note: The symbol “∗” represents the customer site where the end point of the last task coincides with the start point of the next task.Figure 10
Number of trailers transported by the tractor in the exiting drop and pull plan.Figure 11
Number of trailers transported by the tractor in the optimized drop and pull plan.From the generated task waiting time (Tables8 and 9), it can be seen that compared to the existing drop and pull scheme, only 7 tasks have waiting time (task 5, task 39, task 47, task 53, task 59, task 67, and task 73), the number of tasks with waiting time in the optimized drop and pull scheme reached 17, and the total waiting time increased from 4.8 to 19.8, as is shown in Figure 12. This phenomenon is reasonable because under the premise that the number of tasks remains unchanged, the reduction in the number of tractors will inevitably lead to an increase in the number of tasks undertaken by each tractor, which will lead to the waiting time of the trailers.Table 8
Task waiting time in the existing drop and pull scheme.
Task numberWaiting timeTask numberWaiting timeTask numberWaiting timeTask numberWaiting timeTask numberWaiting time1016031046061020170320470.8 h620301803304806304019034049064051.0 h2003505006506021036051066070220370520670.2 h80230380530.5 h68090240390.6 h540690100250400550700110260410560710120270420570720130280430580731.1 h140290440590.6 h01503004506000Table 9
Task waiting time in the optimized drop and pull scheme.
Task numberWaiting timeTask numberWaiting timeTask numberWaiting timeTask numberWaiting timeTask numberWaiting time10.8 h161.0 h311.5 h460.2 h611.6 h20171.0 h321.2 h4706203018033048063040190340490640.8 h5020035050065060211.0 h36051066071.5 h22037052067080230380530681.6 h90241.0 h390540.8 h690100250400550700110260411.8 h560710120270420572.0 h720130280430580.5 h730140.6 h29044059001503004506000Figure 12
Comparison of task waiting time.


### 6.3. Algorithm Validation

To verify the performance of the model and algorithm, in this section, we created 8 groups of calculation examples for drop and pull transportation networks and compared the improved ACS algorithm used in this paper with the PSO and NSGA-III algorithms. The parameters of the improved ACS algorithm are the same as mentioned above, and the parameters of PSO and NSGA-III are set defaulted. These instances are referenced in the form of n-k-d, such as 1-8-50 corresponding to the situation of 1 drop and pull center, 8 customer sites, and 50 trailers to be delivered. In the first four groups of labor instances, we create the drop and pull transport topology network, which is the same as that of Anji Logistics Enterprise. The transportation demand of the semitrailer is obtained by randomly generating customer nodes. In the first four groups of labor instances, we consider the development of the distribution network of logistics enterprises and the increase in customer nodes, and the transportation demand of the semitrailer is also obtained randomly.Table10 shows the comparison of the above three algorithms in solving problems of different scales. We recorded the objective function value and CPU running times of the ACS algorithm, PSO algorithm, and NSGA-III algorithm when solving these instances.Table 10
Performance comparison of CPLEX and the ACS algorithm.
InstancesACSPSONSGAIIIBestA_CPU/SBestA_CPU/SOptiCPU/S1-8-5063245.23.768625.34.667984.33.91-8-100113564.16.1118333.87.8115835.46.91-8-150144926.810.2158231.112.5156405.011.01-8-200198354.915.3208074.319.3204702.316.11-15-250254965.732.4275065.039.9260108.031.41-15-300301893.539.8334437.645.7317290.141.81-25-400503285.472.9537005.583.3524926.770.01-35-5006385668.0132.66933750.1149.76884835.4142.6As shown in Table10, the optimal solution obtained by the improved ACS algorithm is better than those obtained by the PSO and the NSGA-III algorithms. The quality differences of these solutions range from 1.12% to 10.78%.In terms of calculation time, the efficiency of the improved ACS algorithm and the NSGA-III algorithm is higher than that of the PSO algorithm, but there is no significant difference between them. These results verify the effectiveness of the proposed improved ACS algorithm. It also shows the superiority of finding the optimal solution when dealing with large-scale problems.


## 6.1. Basic Experiments for an Idealized Tractor and Semitrailer System

Anji Logistics Enterprise includes 1 drop and pull center and 8 customer sites. According to the data received on one implementation day, a total of 73 drop and pull tasks (73 trailers) need to be performed, which constitute the taskQ of the drop and pull transport network.The relevant parameters are as follows: The average travel speed of the heavy-load tractor isv1=40 km/h, the no-load driving speed is v2=60 km/h, the daily fixed cost is c0=500 RMB/unit, the heavy-load driving cost of the tractor is c1=2.4 RMB/km, the no-load driving cost is c2=2.0 RMB/km, and the waiting cost is c3=1.5 RMB/hour. The transportation distance between each node is shown in Table 3. The transportation demand of each node and the corresponding time window limit-related data refer to the transportation account of Anji Logistics Enterprise in September 2021, as shown in Tables 4 and 5, respectively.Table 3
Distance matrix between sites of drop and pull transport network (unit: km).
0123456780—6072726090108132162160—549078120102787227254—10290120102787237290102—7278426090460789072—543658785901081207854—13842726108901024236138—78487132727860484278—42816278729078724842—Table 4
Transportation demand between sites of drop and pull transportation network (unit: vehicle).
123456781—020302321—1312313—2102042—3212531—2236212—237213—281132—Table 5
Time window for drop and pull transport operations (unit: hour).
123456781——[12, 17]—[13, 17]—[11, 15][12, 17]2[9, 15]—[9, 12][8, 11][9, 14][8, 12][10, 15][12, 16]3—[10, 15][8, 12]—[12, 17]—4[10, 15]—[9, 12][11, 15][8, 11][10, 14]5[11, 16][10, 15]—[9, 12][10, 17][12, 18]6[10, 16][12, 16][9, 14]—[10, 15][11, 16]7[8, 12][12, 15][10, 16]—[8, 12]8[11, 16][12, 18][12, 16][9, 15]—


## 6.2. Experiments for Anji Logistics Enterprise in Chengdu

We use the MATLAB software algorithm, where the parameters of the ACO algorithm are set as follows: the number of antsm=22, the pheromone importance parameter alpha=1, the heuristic factor importance parameter beta=4, the pheromone evaporation coefficient rho=0.2, the pheromone increase intensity coefficient Q=20, and the maximum number of iterations of the algorithm NC_max=130.It can be seen that the ant colony algorithm has good convergence in solving the proposed model and the gradually stable optimization results are shown in Figure6. The total running time of the algorithm is approximately 16.3 s, and the algorithm remains stable when the number of iterations reaches approximately 30. The total cost of the entire drop and pull system is approximately 6.83 × 104 RMB.The function values of each sub-objective are shown in Figures7–9 with the convergence of the algorithm iteration. Figure 7 shows the convergence of the number of tractors with the algorithm iteration. After the algorithm converges, the number of tractors is 22. Figure 8 shows the convergence of the total waiting time of the tractor with the algorithm iteration. After the algorithm converges, the total waiting time of the tractor is 19.8 hours. Figure 9 shows the convergence of the running mileage of the tractor with the algorithm iteration. After the algorithm converges, the running mileage of the tractor is approximately 13,270 kilometers. Judging from the curve convergence of the above three objectives, the convergence curve of the number of tractors is most similar to the convergence curve of the total cost of the drop and pull system because in the comprehensive cost of the drop and pull system, the cost of tractor purchase occupies the largest proportion.Figure 7
Convergence curve with the objective of vehicle number.Figure 8
Convergence curve with the objective of vehicle waiting time.Figure 9
Convergence curve with the objective of running mileage.Compared with the current drop and pull scheme (as shown in Tables6 and 7), the overall cost of the optimized drop and pull scheme is reduced by 15,776 RMB, which is 18.7% lower than the exiting scheme. On the premise of completing the coupling task in strict accordance with the time window limit, the number of tractors required is reduced from 51 to 22. In the exiting drop and pull scheme of the tractor, the ratio of the number of tractors to trailers is approximately 1 : 1.43, each tractor performs 1 to 2 drop and pull tasks (Figure 10), and the average travel distance of the tractor is approximately 329.1 km. In the optimized drop and pull scheme of the tractor, the ratio of the number of tractors to trailers is approximately 1 : 3.31, most tractors perform 3 to 5 drop and pull tasks (Figure 11), and the average tractor travel distance is approximately 603.2 km. The running distance of each tractor has been doubled, which greatly reduces the number of tractors equipped on the premise that all semitrailer distribution tasks are completed according to the time window requirements.Table 6
The exiting drop and pull scheme of the tractor.
Tractor numberPerformance tasks and travel sitesTractor numberPerformance tasks and travel sites17-5 (0-2-8-2-6-0)2720-2 (0-3-8-2-4-0)24-53 (0-2-6-7-5-0)2815-35 (0-3-5∗-8-0)33 (0-2-6-0)2922-26 (0-3-9-4-8-0)443 (0-6-7-0)3029 (0-5-3-0)540 (0-6-2-0)3158 (0-7-9-0)661 (0-8-5-0)3236 (0-5-9-0)751 (0-7-4-0)3319 (0-3-8-0)89-45 (0-2-9-6-8-0)3470 (0-9-4-0)972-47 (0-9-6∗-9-0)3518-66 (0-3-7-8-9-0)1030-11 (0-5-6-3-2-0)3660-1 (0-8-3-2-4-0)1141 (0-6-4-0)3762 (0-8-6-0)1254 (0-7-8)3832 (0-5-6-0)136-73 (0-2-8-9-6-0)3913 (0-3-5-0)1423-39 (0-4-5-6-2-0)4050 (0-7-3-0)1531-71 (0-5-6-9-4-0)4157 (0-7-9-0)1649 (0-7-3-0)4244 (0-6-8-0)1748-67 (0-6-9∗-2-0)4363-10 (0-8-6-2-9-0)1825-42 (0-4-6∗-7-0)4464-46 (0-8-6∗-9-0)1969 (0-9-4-0)4556-12 (0-7-9-3-4-0)2024 (0-4-5-0)4627 (0-4-8-0)2128 (0-5-3-0)4768 (0-9-3-0)2255 (0-7-8-0)4834 (0-5-7-0)2321-59 (0-3-8∗-3-0)4952-65 (0-7-5-8-9-0)2416-37 (0-3-6-5-9-0)5014-38 (0-3-5-6-2-0)258 (0-2-9-0)5133 (0-2-9-0)2617 (0-2-6-0)Vehicle informationNumber of tractors 51, number of trailers 73, rate 1 : 1.43Total cost84143Note: The symbol “∗” represents the customer site where the end point of the last task coincides with the start point of the next task.Table 7
The optimized drop and pull scheme of the tractor.
Tractor numberPerformance tasksTravel sites128-14-69-120-5-3∗-5-3-5-3-5-0259-73-22-430-8-3-9-6-9-6-9-6-0332-10-20-500-5-6-2-9-2-9-2-9-044-58-540-2-6-7-9-7-9-0571-7-600-9-4-2-8-2-8-069-720-2-9∗-6-0737-56-350-5-9-7-9-7-9-081-70-44-460-2-4-9-4-9-4-9-4-0923-18-680-4-5-3-7-3-7-01047-13-390-6-9-3-5-3-5-01153-41-3-360-7-5-6-4-6-4-6-4-01257-63-62-66-490-7-9-8-6-8-6-8-6-8-6-0138-6-240-2-9-2-8-2-8-01464-38-300-8-6∗-2-6-2-0152-400-2-4-6-2-01652-42-110-7-5-6-7-6-7-01745-21-160-6-8-3-8-3-8-01817-27-150-3-7-4-8-4-8-01961-31-51-330-8-5∗-6-5-6-5-6-02055-5-260-7-8-2-6-2-6-02148-67-34-190-6-9∗-2-9-2-9-2-02229-25-650-5-3-4-6-4-6-0Vehicle informationNumber of tractors 22, number of trailers 73, rate 1 : 3.31Total cost68367Note: The symbol “∗” represents the customer site where the end point of the last task coincides with the start point of the next task.Figure 10
Number of trailers transported by the tractor in the exiting drop and pull plan.Figure 11
Number of trailers transported by the tractor in the optimized drop and pull plan.From the generated task waiting time (Tables8 and 9), it can be seen that compared to the existing drop and pull scheme, only 7 tasks have waiting time (task 5, task 39, task 47, task 53, task 59, task 67, and task 73), the number of tasks with waiting time in the optimized drop and pull scheme reached 17, and the total waiting time increased from 4.8 to 19.8, as is shown in Figure 12. This phenomenon is reasonable because under the premise that the number of tasks remains unchanged, the reduction in the number of tractors will inevitably lead to an increase in the number of tasks undertaken by each tractor, which will lead to the waiting time of the trailers.Table 8
Task waiting time in the existing drop and pull scheme.
Task numberWaiting timeTask numberWaiting timeTask numberWaiting timeTask numberWaiting timeTask numberWaiting time1016031046061020170320470.8 h620301803304806304019034049064051.0 h2003505006506021036051066070220370520670.2 h80230380530.5 h68090240390.6 h540690100250400550700110260410560710120270420570720130280430580731.1 h140290440590.6 h01503004506000Table 9
Task waiting time in the optimized drop and pull scheme.
Task numberWaiting timeTask numberWaiting timeTask numberWaiting timeTask numberWaiting timeTask numberWaiting time10.8 h161.0 h311.5 h460.2 h611.6 h20171.0 h321.2 h4706203018033048063040190340490640.8 h5020035050065060211.0 h36051066071.5 h22037052067080230380530681.6 h90241.0 h390540.8 h690100250400550700110260411.8 h560710120270420572.0 h720130280430580.5 h730140.6 h29044059001503004506000Figure 12
Comparison of task waiting time.


## 6.3. Algorithm Validation

To verify the performance of the model and algorithm, in this section, we created 8 groups of calculation examples for drop and pull transportation networks and compared the improved ACS algorithm used in this paper with the PSO and NSGA-III algorithms. The parameters of the improved ACS algorithm are the same as mentioned above, and the parameters of PSO and NSGA-III are set defaulted. These instances are referenced in the form of n-k-d, such as 1-8-50 corresponding to the situation of 1 drop and pull center, 8 customer sites, and 50 trailers to be delivered. In the first four groups of labor instances, we create the drop and pull transport topology network, which is the same as that of Anji Logistics Enterprise. The transportation demand of the semitrailer is obtained by randomly generating customer nodes. In the first four groups of labor instances, we consider the development of the distribution network of logistics enterprises and the increase in customer nodes, and the transportation demand of the semitrailer is also obtained randomly.Table10 shows the comparison of the above three algorithms in solving problems of different scales. We recorded the objective function value and CPU running times of the ACS algorithm, PSO algorithm, and NSGA-III algorithm when solving these instances.Table 10
Performance comparison of CPLEX and the ACS algorithm.
InstancesACSPSONSGAIIIBestA_CPU/SBestA_CPU/SOptiCPU/S1-8-5063245.23.768625.34.667984.33.91-8-100113564.16.1118333.87.8115835.46.91-8-150144926.810.2158231.112.5156405.011.01-8-200198354.915.3208074.319.3204702.316.11-15-250254965.732.4275065.039.9260108.031.41-15-300301893.539.8334437.645.7317290.141.81-25-400503285.472.9537005.583.3524926.770.01-35-5006385668.0132.66933750.1149.76884835.4142.6As shown in Table10, the optimal solution obtained by the improved ACS algorithm is better than those obtained by the PSO and the NSGA-III algorithms. The quality differences of these solutions range from 1.12% to 10.78%.In terms of calculation time, the efficiency of the improved ACS algorithm and the NSGA-III algorithm is higher than that of the PSO algorithm, but there is no significant difference between them. These results verify the effectiveness of the proposed improved ACS algorithm. It also shows the superiority of finding the optimal solution when dealing with large-scale problems.


## 7. Conclusion

This paper studies the road drop and pull transportation system and proposes a method for configuring the number of tractors and semitrailers based on tractor routing optimization, which is used for the daily scheduling operation of tractors. In addition, we take the succession of drop and pull tasks and the specified delivery time of the tractor continuous towing semitrailer into account. An ant colony search heuristic algorithm is designed to solve this problem, which can obtain the optimal solution in an acceptable time. The applicability of the improved ACO algorithm in dealing with large-scale problems is verified through the test of the real example of the Anji Logistics Enterprise. Compared to the traditional method, the optimization method proposed in this paper can obtain a better tractor routing scheme and reduce the number of tractor configurations on the basis of ensuring the timely delivery of semitrailers. It can also make truck connection times meet the transit time requirements of station traffic, reducing potential train delays. Therefore, a tractor routing scheme that can meet basic needs is sufficient to obtain a relatively optimal number of tractors and semitrailers.In future research, we can further consider the problem of the quantity configuration of tractors and semitrailers under various vehicle types.



---

*Source: 3017196-2022-10-05.xml*