# Reverse Logistics Vehicle Routing Optimization Problem Based on Multivehicle Recycling

Authors: Zhaohui Gao; Caiyun Ye
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In the reverse logistics recycling process, considering the diversity of recycling types, a variety of vehicle models are used to meet the reverse logistics recycling requirements. Therefore, this paper considers the fixed costs, transportation costs, carbon emission costs during driving, and time penalty costs in the reverse logistics process under multiple constraints such as multiple vehicle types and time windows in the recycling center. The recovery point is the recovery model, and an improved genetic algorithm is used to solve it. Drawing lessons from the idea of greed, the superiority of the initial population is improved; the entry matrix and the exit matrix of the iterative population are constructed, and the crossover operator is improved based on this, and the forward insertion method is introduced to design the hybrid crossover operation to speed up the population. At the same time, the improvement of the mutation operator is proposed to increase the diversity of the population. The experimental results show that the multivehicle mixed delivery mode can reduce costs more effectively than single-vehicle models, and the improved genetic algorithm has better convergence and stability.


---

## Body

## 1. Introduction

In recent years, with the shortage of natural resources, how to maximize the use of existing resources has become a hot issue that countries around the world pay close attention to. The emergence of reverse logistics can relieve the pressure on natural resources to a certain extent and increase the availability of goods. Optimizing the recycling plan, improving the efficiency of product recycling, and reducing recycling costs are of great significance to improving recycling efficiency.Reverse logistics refers to the reverse flow of scrapped products from customers to the starting point for disposal or remanufacturing purposes. The recycling center uses vehicles of different models to collect recyclable products from customers and recycle them to the recycling point. The recycling center is responsible for recycling products and preliminary processing of reusable products. For cost-saving reasons, recycling points can establish partnerships with recycling centers that are closer. However, due to the complexity of the logistics network and environmental impact, the transportation of recycled products has brought a heavy burden to the company. The local government encourages companies to carry out recycling operations through laws and advertisements to reduce resource consumption. The implementation of the reverse supply chain management mechanism can improve the efficiency of the recycling network, reduce the level of pollution caused by waste products, and promote the clean and environmentally friendly development of world cities. In practice, distance is an important factor affecting product recycling. By evaluating the location of the recycling center relative to the recycling point, it is found that the recycling operation is costly. Therefore, neglected waste constitutes a source of serious environmental problems and interferes with people’s daily life to a certain extent. Taking into account the particularity of the recycling business, optimizing the recycling process can improve the efficiency of the entire network while reducing costs and pollution.


## 2. Literature Review

Regarding the path optimization of reverse logistics, many scholars at home and abroad have done research. For example, Chaabane et al. [1] established a mathematical model for the recycling problem of scrapped vehicles, combining the classic vehicle routing problem and the collection and delivery problem, as well as the constraints of multiple vehicle types and time windows. Foroutan et al. [2] aimed at minimizing operating costs and environmental costs, taking into account the return and lead time and delay costs, and established a mixed-integer nonlinear programming model for the routing and scheduling of multimodel green vehicles. Chen et al. [3] used an improved ant colony algorithm to solve the vehicle configuration and route optimization model that minimizes the recovery task. Mishra et al. [4] used the form of cooperative alliance to realize the limited means of vehicle route optimization in the reverse logistics network. The cooperative mechanism can help avoid the ineffective allocation of resources, reduce the operation of recycling logistics, and reduce long-distance transportation. Carlos et al. [5] considered the dangers in the process of recycling e-waste and carried out recycling, modeling the reverse logistics process of electrical and electronic equipment as a biobjective mixed-integer programming model under uncertainty. Chen et al. [6] proposed a nonlinear optimization model involving the number of second-hand products and reprocessed products. For these two types of requirements, analysis and insights are provided in the form of a complete strategy, which consists of different scenarios and can make the best decision under variable conditions. Numerical examples supplement insights into the model by performing sensitivity analysis on relevant model parameters. In order to minimize the total cost, Patrik and Klaudia [7] established a time window to recycle the heterogeneous fleet electric vehicle path model under consideration of vehicle load constraints; the vehicle type limits the weight of recyclable waste and the services allowed by customers’ time limit. Samantha et al. [8] used reverse logistics to determine the resources needed to reuse IOT for road infrastructure and modeled reverse logistics to transport the Internet of Things from the tailings dam to the processing plant and then to the road construction site. Cao et al. [9] studied Slovakia’s green and reverse logistics and found that the dominant position in Slovakia’s green and reverse logistics was achieved by large-scale production companies in the automobile industry in the west. Lechner and Reimann [10] established a multiangle MADM framework to provide systematic decision support for enterprises to choose the best 3PRLP. Saleh Moslehi et al. [11] evaluated the feasibility of a sustainable “reverse logistics” process in Brazil’s mobile phone manufacturing industry and conducted research on actual cases of returned mobile phones from one of Brazil’s largest mobile phone manufacturers. Wang et al. [12] designed a hybrid method based on CRITIC and EDAS methods and FFS to solve the needs of sustainable third-party reverse logistics providers.There has also been some in-depth research on the path optimization problem of multivehicles with time constraints. For example, Ge and Yin [13] verified that cross-docking operations with multiple vehicle types can effectively improve the operating efficiency of supermarket chains and reduce logistics costs. Guo et al. [14] established a multimodel electric vehicle path optimization model considering the differentiated service cost under factors such as vehicle diversity, charging strategy, human-vehicle matching, and service time differentiation. Zhang et al. [15] proposed a new multiagent attention model to solve the multivehicle routing problem with soft time windows. Fan et al. [16] designed a genetic variable neighborhood algorithm by improving the adaptive search strategy for the vehicle routing optimization problem of multivehicles with fuzzy collection requirements. Yue et al. [17] considered transportation risks and transportation costs and constructed a multiobjective multivehicle path optimization model. Xu et al. [18] comprehensively considered factors such as multiple depots, multiple models, multiple goods, mismatched supply and demand among customers, and arbitrarily splitting of delivery and delivery requirements in order to optimize the multipoint production material allocation system and studied the routing problem of delivery vehicles. The research of Nicola et al. [19] included selecting suppliers and routing homogenous vehicle fleet to purchase different products from the selected suppliers to meet the minimization of transportation and procurement costs, define new branching rules, introduce new inequality families, and prove the new branch price-cutting method is very competitive. Appiah et al. [20] used a mixed-integer quadratic programming model to optimize the distribution of goods from 105 distributors in two factories in Ghana. Glize et al. [21] embedded a method for accurately solving its biobjective counterparts with ℇ constraints and proved that the modified method is stronger than the next set provided by the most advanced methods obtained from the literature.It can be seen from the above literature that there have been many studies on reverse logistics, and many domestic and foreign scholars have conducted various research studies on reverse logistics. There have also been different aspects of research on multivehicle path optimization. However, there is no research on path optimization for multiple vehicles in the recycling process.Therefore, according to the characteristics of recycled products and the impact of time constraints on the economic and social benefits of enterprises, multiple vehicles will be used for recycling and distribution, and a reverse logistics path optimization model under the time window will be constructed, which is more in line with actual needs. And because of the complexity of the path optimization problem, genetic algorithm is used to solve it.


## 3. Problem Statement and Model Formulation

### 3.1. Problem Description

A recycling centerD has M types of vehicles, and the corresponding vehicle load capacity is Qmm∈1,2,…,M), and there are km vehicles of various types. Different types of vehicles start from the recycling center to recycle several recycling points. It is assumed that the recycling volume of each recycling point does not exceed the load of the vehicle, and the total recovery of each subpath does not exceed the load of the vehicle. The vehicle returns to the recycling center after completing the task. The situation that meets the needs of recycling points and minimizes the total cost is solved, and the most suitable path is found through models and algorithms to minimize the cost of recycling centers; it is obvious from Figure 1.Figure 1
Schematic diagram of recycling companies recycling products from recycling points.


### 3.2. Basic Assumption

Based on the above problem description, the following assumptions are made:(1)
There is only one recycling center, its inventory is large enough, and there are multiple recycling vehicles of different models.(2)
Each model has a different rated load, fixed cost and driving cost.(3)
The total amount of recycling at the recycling point does not exceed the vehicle capacity limit.(4)
The driving speed of the vehicle is uniform.(5)
The recycling task only involves the recycling of goods, that is, one-way flow.(6)
The request for recycling vehicles must be issued from the recycling center and returned.(7)
Recycling points are all serviced and only receive one service. The geographic location, recycling volume, and service time range of all recycling points are known and fixed.(8)
Each vehicle has a daily working time limit.(9)
Each recycling point can only issue one order, and recycling companies can accept multiple orders within their capabilities.(10)
The point to be recycled has its own recycling volume and recycling time window.(11)
Recycling vehicles should arrive at the collection point within the collection time window specified by the customer. If they arrive after the time window, overtime penalty costs must be paid; if they arrive before the time window, they must wait until the start time of the time window of the collection point.


### 3.3. Symbol Description

N: collection point collection, 0,i,j∈N, where 0 is the recycling centerM: there are m types of vehicles, m∈MKm: the available number of vehicle types m is k, k∈KmQm: the maximum load capacity of model mTm: maximum daily working hours of model mC1m: fixed cost of model mC2m: unit transportation cost of model mC3m: the carbon cost of CO2 emissions per unit distance travelled by model mw: CO2 emission factordij: distance from recovery point i to recovery point jtij: travel time from collection point i to collection point jβ: late penalty factorETi,LTi: recycling point i provides the best recycling service time window for recycling companiesQi: recycling point i needs to recycleqki: current load capacity of vehicle k at collection point iT: maximum daily working hours per vehiclexijk: 0-1 variable; vehicle k passes through recycling point j from recycling company i


## 3.1. Problem Description

A recycling centerD has M types of vehicles, and the corresponding vehicle load capacity is Qmm∈1,2,…,M), and there are km vehicles of various types. Different types of vehicles start from the recycling center to recycle several recycling points. It is assumed that the recycling volume of each recycling point does not exceed the load of the vehicle, and the total recovery of each subpath does not exceed the load of the vehicle. The vehicle returns to the recycling center after completing the task. The situation that meets the needs of recycling points and minimizes the total cost is solved, and the most suitable path is found through models and algorithms to minimize the cost of recycling centers; it is obvious from Figure 1.Figure 1
Schematic diagram of recycling companies recycling products from recycling points.


## 3.2. Basic Assumption

Based on the above problem description, the following assumptions are made:(1)
There is only one recycling center, its inventory is large enough, and there are multiple recycling vehicles of different models.(2)
Each model has a different rated load, fixed cost and driving cost.(3)
The total amount of recycling at the recycling point does not exceed the vehicle capacity limit.(4)
The driving speed of the vehicle is uniform.(5)
The recycling task only involves the recycling of goods, that is, one-way flow.(6)
The request for recycling vehicles must be issued from the recycling center and returned.(7)
Recycling points are all serviced and only receive one service. The geographic location, recycling volume, and service time range of all recycling points are known and fixed.(8)
Each vehicle has a daily working time limit.(9)
Each recycling point can only issue one order, and recycling companies can accept multiple orders within their capabilities.(10)
The point to be recycled has its own recycling volume and recycling time window.(11)
Recycling vehicles should arrive at the collection point within the collection time window specified by the customer. If they arrive after the time window, overtime penalty costs must be paid; if they arrive before the time window, they must wait until the start time of the time window of the collection point.


## 3.3. Symbol Description

N: collection point collection, 0,i,j∈N, where 0 is the recycling centerM: there are m types of vehicles, m∈MKm: the available number of vehicle types m is k, k∈KmQm: the maximum load capacity of model mTm: maximum daily working hours of model mC1m: fixed cost of model mC2m: unit transportation cost of model mC3m: the carbon cost of CO2 emissions per unit distance travelled by model mw: CO2 emission factordij: distance from recovery point i to recovery point jtij: travel time from collection point i to collection point jβ: late penalty factorETi,LTi: recycling point i provides the best recycling service time window for recycling companiesQi: recycling point i needs to recycleqki: current load capacity of vehicle k at collection point iT: maximum daily working hours per vehiclexijk: 0-1 variable; vehicle k passes through recycling point j from recycling company i


## 4. Model Building

### 4.1. Analysis of Each Cost of Reverse Logistics

Taking into account various costs in the recycling process, including transportation costs and recycling costs, carbon emission costs, and time penalty costs, the problem studied in this article can be described as recycling centers from multiple recycling points.(1)minZ=Z1+Z2+Z3+Z4.The detailed steps of each part of the cost are as follows.


#### 4.1.1. Fixed Cost of Vehicles

The fixed cost of recycling vehicles is usually constant including vehicle depreciation, insurance, annual inspection fees, road and bridge fees, and driver’s wages and other costs related to delivery vehicles. The fixed vehicle costZ1 is as follows:(2)Z1=∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk.


#### 4.1.2. Variable Transportation Costs of Vehicles

The transportation variable cost of a distribution vehicle is usually the same as the mileage of the vehicle. Therefore, the transportation variable cost of a distribution vehicleZ2 can be expressed as(3)Z2=∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk⋅dij.


#### 4.1.3. Carbon Emission Cost

The cost of carbon emissions mainly refers to the cost of CO2 emissions produced by vehicles consuming fuel during the distribution process; carbon emissions = fuel consumption × CO2 emission coefficient [22]. Fuel consumption is not only related to transportation distance but also related to vehicle load. According to literature [22], a linear function related to the fuel consumption per unit distance ρ and the weight of the cargo vehicle is obtained, where Qm is the maximum cargo capacity of the vehicle, the cargo capacity of the cargo vehicle is X, and the fuel consumption per unit distance is ρ∗ when fully loaded. The fuel consumption per unit distance at load time is ρ0.Then, the fuel consumption per unit distanceρX is as follows:(4)ρX=ρ0+ρ∗−ρ0QmX.Therefore, the carbon emission costZ3 in the reverse logistics process of multivehicle models can be expressed as follows:(5)Z3=∑m=0M∑k=1Km∑i=0N∑j=0Nw⋅C1m⋅xijmk⋅dij⋅ρqki.


#### 4.1.4. Time Penalty Cost

Since the collection point has requirements for the collection time, the collection vehicles are required to arrive within the prescribed time period, but due to many other reasons, the collection vehicles often cannot arrive on time, which will incur a certain penalty cost, so the penalty cost isPi:(6)Pi=C1∗ETi−tikm,tij<ETi,0,ETi≤tij≤LTi;∀i∈N′,C2,tij>LTi.The time window constraint allows the vehicle to arrive earlier thanETi, so the waiting time is ωikm=ETi−tikm, but the arrival time is earlier than the time window, one needs to bear a certain penalty fee, C1 is the penalty factor, and C2 is a very large positive number.In summary, the vehicle path optimization model for reverse logistics recycling considering multiple vehicle types is(7)minZ=Z1+Z2+Z3+Z4=∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk+∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk⋅dij+∑m=0M∑k=1Km∑i=0N∑j=0Nw⋅C3m⋅xijmk⋅dij⋅ρqki+∑m=0M∑k=1Km∑i=0N∑j=0NxijmkPi,(8)s.t.∑i=0N∑m=0M∑k=1Kmxijmk=1,j∈N,(9)∑i=0N∑m=0M∑k=1Kmxijmk≥1,j∈N,(10)∑i=0N∑k=1Kmxilmk≥∑i=0N∑k=1Kmxljmk,l∈N,j∈N,i≠j,(11)∑i=0N∑j=0Nxijmk≤1,k∈K,(12)∑j=1N∑k=1Kmx0jmk≤Km,m∈M,(13)∑i=1N∑m=1Mxijmk⋅qki≤Qm,k∈Km,j∈N,(14)∑i=0N∑m=1Kmxijmk⋅tij≤Tm,j∈N,(15)xijmk=0,1,i∈N,j∈N,k∈Km,m∈M.Equation (8) means that each recycling point can only be passed by the recycling vehicle once at most; equation (9) is used to restrict the existence of recycling centers in multiple distribution routes; equation (10) is used to restrict entry and exit from a certain recycling point. The vehicles at the recycling point are the same vehicle; formula (11) is used to restrict the number of times each vehicle can be recycled to any recycling point not more than once; formula (12) indicates that the number of vehicles used in each type of recycling center should not exceed the available number of vehicles of this type; equation (13) indicates that the total recovery volume of all collection points in each route meets the vehicle capacity limit; equation (14) indicates that the running time of each vehicle cannot exceed the maximum transportation time; equation (15) is the decision variable constraints.


## 4.1. Analysis of Each Cost of Reverse Logistics

Taking into account various costs in the recycling process, including transportation costs and recycling costs, carbon emission costs, and time penalty costs, the problem studied in this article can be described as recycling centers from multiple recycling points.(1)minZ=Z1+Z2+Z3+Z4.The detailed steps of each part of the cost are as follows.


### 4.1.1. Fixed Cost of Vehicles

The fixed cost of recycling vehicles is usually constant including vehicle depreciation, insurance, annual inspection fees, road and bridge fees, and driver’s wages and other costs related to delivery vehicles. The fixed vehicle costZ1 is as follows:(2)Z1=∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk.


### 4.1.2. Variable Transportation Costs of Vehicles

The transportation variable cost of a distribution vehicle is usually the same as the mileage of the vehicle. Therefore, the transportation variable cost of a distribution vehicleZ2 can be expressed as(3)Z2=∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk⋅dij.


### 4.1.3. Carbon Emission Cost

The cost of carbon emissions mainly refers to the cost of CO2 emissions produced by vehicles consuming fuel during the distribution process; carbon emissions = fuel consumption × CO2 emission coefficient [22]. Fuel consumption is not only related to transportation distance but also related to vehicle load. According to literature [22], a linear function related to the fuel consumption per unit distance ρ and the weight of the cargo vehicle is obtained, where Qm is the maximum cargo capacity of the vehicle, the cargo capacity of the cargo vehicle is X, and the fuel consumption per unit distance is ρ∗ when fully loaded. The fuel consumption per unit distance at load time is ρ0.Then, the fuel consumption per unit distanceρX is as follows:(4)ρX=ρ0+ρ∗−ρ0QmX.Therefore, the carbon emission costZ3 in the reverse logistics process of multivehicle models can be expressed as follows:(5)Z3=∑m=0M∑k=1Km∑i=0N∑j=0Nw⋅C1m⋅xijmk⋅dij⋅ρqki.


### 4.1.4. Time Penalty Cost

Since the collection point has requirements for the collection time, the collection vehicles are required to arrive within the prescribed time period, but due to many other reasons, the collection vehicles often cannot arrive on time, which will incur a certain penalty cost, so the penalty cost isPi:(6)Pi=C1∗ETi−tikm,tij<ETi,0,ETi≤tij≤LTi;∀i∈N′,C2,tij>LTi.The time window constraint allows the vehicle to arrive earlier thanETi, so the waiting time is ωikm=ETi−tikm, but the arrival time is earlier than the time window, one needs to bear a certain penalty fee, C1 is the penalty factor, and C2 is a very large positive number.In summary, the vehicle path optimization model for reverse logistics recycling considering multiple vehicle types is(7)minZ=Z1+Z2+Z3+Z4=∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk+∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk⋅dij+∑m=0M∑k=1Km∑i=0N∑j=0Nw⋅C3m⋅xijmk⋅dij⋅ρqki+∑m=0M∑k=1Km∑i=0N∑j=0NxijmkPi,(8)s.t.∑i=0N∑m=0M∑k=1Kmxijmk=1,j∈N,(9)∑i=0N∑m=0M∑k=1Kmxijmk≥1,j∈N,(10)∑i=0N∑k=1Kmxilmk≥∑i=0N∑k=1Kmxljmk,l∈N,j∈N,i≠j,(11)∑i=0N∑j=0Nxijmk≤1,k∈K,(12)∑j=1N∑k=1Kmx0jmk≤Km,m∈M,(13)∑i=1N∑m=1Mxijmk⋅qki≤Qm,k∈Km,j∈N,(14)∑i=0N∑m=1Kmxijmk⋅tij≤Tm,j∈N,(15)xijmk=0,1,i∈N,j∈N,k∈Km,m∈M.Equation (8) means that each recycling point can only be passed by the recycling vehicle once at most; equation (9) is used to restrict the existence of recycling centers in multiple distribution routes; equation (10) is used to restrict entry and exit from a certain recycling point. The vehicles at the recycling point are the same vehicle; formula (11) is used to restrict the number of times each vehicle can be recycled to any recycling point not more than once; formula (12) indicates that the number of vehicles used in each type of recycling center should not exceed the available number of vehicles of this type; equation (13) indicates that the total recovery volume of all collection points in each route meets the vehicle capacity limit; equation (14) indicates that the running time of each vehicle cannot exceed the maximum transportation time; equation (15) is the decision variable constraints.


## 4.1.1. Fixed Cost of Vehicles

The fixed cost of recycling vehicles is usually constant including vehicle depreciation, insurance, annual inspection fees, road and bridge fees, and driver’s wages and other costs related to delivery vehicles. The fixed vehicle costZ1 is as follows:(2)Z1=∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk.


## 4.1.2. Variable Transportation Costs of Vehicles

The transportation variable cost of a distribution vehicle is usually the same as the mileage of the vehicle. Therefore, the transportation variable cost of a distribution vehicleZ2 can be expressed as(3)Z2=∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk⋅dij.


## 4.1.3. Carbon Emission Cost

The cost of carbon emissions mainly refers to the cost of CO2 emissions produced by vehicles consuming fuel during the distribution process; carbon emissions = fuel consumption × CO2 emission coefficient [22]. Fuel consumption is not only related to transportation distance but also related to vehicle load. According to literature [22], a linear function related to the fuel consumption per unit distance ρ and the weight of the cargo vehicle is obtained, where Qm is the maximum cargo capacity of the vehicle, the cargo capacity of the cargo vehicle is X, and the fuel consumption per unit distance is ρ∗ when fully loaded. The fuel consumption per unit distance at load time is ρ0.Then, the fuel consumption per unit distanceρX is as follows:(4)ρX=ρ0+ρ∗−ρ0QmX.Therefore, the carbon emission costZ3 in the reverse logistics process of multivehicle models can be expressed as follows:(5)Z3=∑m=0M∑k=1Km∑i=0N∑j=0Nw⋅C1m⋅xijmk⋅dij⋅ρqki.


## 4.1.4. Time Penalty Cost

Since the collection point has requirements for the collection time, the collection vehicles are required to arrive within the prescribed time period, but due to many other reasons, the collection vehicles often cannot arrive on time, which will incur a certain penalty cost, so the penalty cost isPi:(6)Pi=C1∗ETi−tikm,tij<ETi,0,ETi≤tij≤LTi;∀i∈N′,C2,tij>LTi.The time window constraint allows the vehicle to arrive earlier thanETi, so the waiting time is ωikm=ETi−tikm, but the arrival time is earlier than the time window, one needs to bear a certain penalty fee, C1 is the penalty factor, and C2 is a very large positive number.In summary, the vehicle path optimization model for reverse logistics recycling considering multiple vehicle types is(7)minZ=Z1+Z2+Z3+Z4=∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk+∑m=0M∑k=1Km∑i=0N∑j=0NC1m⋅xijmk⋅dij+∑m=0M∑k=1Km∑i=0N∑j=0Nw⋅C3m⋅xijmk⋅dij⋅ρqki+∑m=0M∑k=1Km∑i=0N∑j=0NxijmkPi,(8)s.t.∑i=0N∑m=0M∑k=1Kmxijmk=1,j∈N,(9)∑i=0N∑m=0M∑k=1Kmxijmk≥1,j∈N,(10)∑i=0N∑k=1Kmxilmk≥∑i=0N∑k=1Kmxljmk,l∈N,j∈N,i≠j,(11)∑i=0N∑j=0Nxijmk≤1,k∈K,(12)∑j=1N∑k=1Kmx0jmk≤Km,m∈M,(13)∑i=1N∑m=1Mxijmk⋅qki≤Qm,k∈Km,j∈N,(14)∑i=0N∑m=1Kmxijmk⋅tij≤Tm,j∈N,(15)xijmk=0,1,i∈N,j∈N,k∈Km,m∈M.Equation (8) means that each recycling point can only be passed by the recycling vehicle once at most; equation (9) is used to restrict the existence of recycling centers in multiple distribution routes; equation (10) is used to restrict entry and exit from a certain recycling point. The vehicles at the recycling point are the same vehicle; formula (11) is used to restrict the number of times each vehicle can be recycled to any recycling point not more than once; formula (12) indicates that the number of vehicles used in each type of recycling center should not exceed the available number of vehicles of this type; equation (13) indicates that the total recovery volume of all collection points in each route meets the vehicle capacity limit; equation (14) indicates that the running time of each vehicle cannot exceed the maximum transportation time; equation (15) is the decision variable constraints.


## 5. Algorithm Design

In the traditional genetic algorithm, the effect of solving the vehicle routing problem of a single parking lot and single vehicle is better. However, in this paper, the two constraints of “multiple vehicle types” and “time window” need to be considered at the same time. The quality of the solution will be affected, and even unsolvable situation exists. The algorithm design used in this article refers to Chenet al.’s [23] research on multidepot and multichromosome genetic algorithm, and on this basis, the “time window” constraint is added, and each individual is set to contain 2 chromosomes-delivery route sequence and vehicle sequence, which means all available vehicles and their delivery routes, effectively avoiding invalid solutions. The following is a detailed introduction of the algorithm.


### 5.1. Solution Encoding

This article uses natural number coding to encode such problems. TheN recycling points are arranged to indicate the order in which the recycling points are passed by the serviced vehicles. It is necessary to insert multiple points representing the recycling companies to divide them into multiple ends to represent multiple routes for multiple vehicles. First, the number of collection points is represented by a natural number j, which represents the jth collection point, and 0 represents a recycling company. First, an ordered sequence of reclaim points is generated, and then n−1 0s are inserted in the sequence to divide the sequence into n segments; each segment represents a service line corresponding to a vehicle, where n represents the number of vehicles. For multivehicle problems, inserting 0 into the sequence cannot distinguish the correspondence relationship between the vehicles type and the lines, so consider replacing them with vehicle numbers. Recycling companies can use vehicle k to represent; let ‐k represent the number of the kth vehicle, ‘‐’ represents the number to distinguish it from the collection point, and ‘k’ represents the kth vehicle [11]. The original feasible solution Food=0,1,2,3,0,4,5,0,6,7 can be expressed as Food=−1,1,2,3,−2,4,5,−3,6,7, and the path it represents is as follows:Vehicle 1: 0-1-2-3-0Vehicle 2: 0-4-5-0Vehicle 3: 0-6-7-0That is, the sequence from one vehicle number to the next vehicle number is the sequence of collection points that this numbered vehicle passes through.


### 5.2. Population Initialization

The fitness of an individual determines the strengths and weaknesses of the individual and determines whether an individual can be retained in the iterative process. According to the individual’s delivery route sequence chromosome and vehicle sequence chromosome, the delivery task is arranged, and the fitness is calculated. The process is as follows:(1)
For thei−th individual in the population, select an available vehicle according to its vehicle sequence chromosome, and then select as many customer points as possible to be delivered in sequence in its delivery route sequence chromosome. The total demand for customer points should not exceed the rated load of the vehicle.(2)
Judge whether all the customer points in the chromosome of the distribution route sequence have been distributed. If there are customer points to be distributed, return to (1); if not, go to (3).(3)
After completing the task distribution, generate the distribution planJi of the i-th individual in the population, and calculate its total cost Zi according to formula (1).(4)
Take the costZi corresponding to the i-th individual, set fi=1/Zi, and fi is the fitness of the i−th individual.Example: suppose the delivery route sequence chromosome of thet-th individual in the population is [4, 5, 6, 3, 1, 2], and the corresponding customer point demand is [300, 200, 200, 400, 100, 300]; the vehicle sequence chromosome is [2, 3, 1, 4, 5], the corresponding model is [1, 2, 2, 3, 3], and the corresponding rated load of the model is [300, 500, 500, 400, 400]; according to the above task allocation method, the assigned tasks are as follows:①
Install vehicles with a sequence number of 2 and model 1, and the service route is 0-4-0②
For vehicles with a sequence number of 3 and model 2, the service route is 0-5-6-0③
For vehicles with a sequence number of 1 and model 2, the service route is 0-3-1-0④
For vehicles with a sequence number of 4 and model 3, the service route is 0-2-0⑤
For other vehicles, distribution tasks are not assignedThen, the total costZt and the fitness degree ft=1/Zt are calculated according to the assigned task and formula (1).


### 5.3. Crossover Operation

Since the variable-point crossing may cause the vehicle to be overloaded, resulting in an illegal solution, this paper adopts a fixed-point single-point crossing, and the crossing point is set after the first gene (vehicle gene). Individuals A and B are randomly selected according to the crossover probabilityPc, and the specific steps for performing crossover operations on them are as follows:(1)
Randomly generate a natural number between 1 andH, representing the same chromosome number of the two individuals to be crossed (the number of individual A is set to a, the number of individual B is set to b, and a = b).(2)
Take out the customer genes with the same two chromosomesa and b, and store them in the gene bank Fa,Fb.(3)
Exchange the customer genes of 2 chromosomes (keep the order of customer genes unchanged).(4)
Compare the client genes of chromosomes other than chromosomea in individual A with the genes of Fb one by one, and delete all the same genes. Similarly, perform similar operations on individual B.(5)
Insert the genes inFa into any position after the first gene of any chromosome of individual A randomly one by one. After that, judge whether the vehicle is overloaded; if it is overloaded, randomly insert the next chromosome, and judge whether it is overloaded again, and so on, until all the genes in Fa are allocated. Perform similar operations on individual B.


### 5.4. Mutation Operation

Suppose the mutation probabilityPe, the first gene of each chromosome of an individual does not generate mutation, and for each other gene i, a floating-point number ri corresponding to gene i is randomly generated between 0 and 1. If ri<Pe, put the gene into the mutation gene bank G, and delete it from the chromosome at the same time; otherwise, this gene will not produce mutation. After that, follow the above step (5) to randomly insert the genes in G into the chromosomes one by one.


### 5.5. Selection Operation

The traditional proportional selection method (the probability of selection is proportional to the fitness of the individual) has some bad properties: in the early stages of iterations, some super individuals with high fitness will dominate the selection process, resulting in excessive selection pressure; in the late stage, the fitness gap between individuals is small, resulting in too little selection pressure. The normalization technique proposed by CHENG and others for the problem of et al. minimization makes up for the above shortcomings, and its form is as follows:(16)fk′=fmax−fk+γfmax−fmin+γ,where fk is the fitness of the individual; fmax is the maximum fitness of the population individual; fmin is the minimum fitness of the population individual; γ is the average fixed cost of the vehicle; and fk′ is the fitness after transformation.The advantage of convertingfk into fk′ is that the survival pressure is always at a relatively moderate position, thereby preventing premature convergence. Then, use roulette to choose: first, calculate the total fitness F=∑fki′; second, calculate the relative probability of individual i, Pri=fki′/F; then, calculate the cumulative probability of individual i, Pei=∑Prjj=1,2,…,i; finally, randomly generate a floating-point number ri in the interval 0 ∼ 1; if ri<Pei, select the first individual; otherwise, choose to make Pei−1<ri≤Pei hold the i-th individual.


### 5.6. Elite Selection

TheS + 1th individual is designed to be initially used to preserve the optimal individual in the initial population. After that, if the fitness of the S + 1th individual is due to all offspring individuals, it is used to replace the worst individual in the offspring; otherwise, it is replaced by the best individual in the offspring. On the one hand, elite selection can ensure that the genes of outstanding individuals are not lost in the process of evolutionary selection, thereby accelerating convergence; on the other hand, it ensures that the optimal individual in the offspring population will not be worse than the parent population, thus making the evolutionary curve monotonously decreasing.


## 5.1. Solution Encoding

This article uses natural number coding to encode such problems. TheN recycling points are arranged to indicate the order in which the recycling points are passed by the serviced vehicles. It is necessary to insert multiple points representing the recycling companies to divide them into multiple ends to represent multiple routes for multiple vehicles. First, the number of collection points is represented by a natural number j, which represents the jth collection point, and 0 represents a recycling company. First, an ordered sequence of reclaim points is generated, and then n−1 0s are inserted in the sequence to divide the sequence into n segments; each segment represents a service line corresponding to a vehicle, where n represents the number of vehicles. For multivehicle problems, inserting 0 into the sequence cannot distinguish the correspondence relationship between the vehicles type and the lines, so consider replacing them with vehicle numbers. Recycling companies can use vehicle k to represent; let ‐k represent the number of the kth vehicle, ‘‐’ represents the number to distinguish it from the collection point, and ‘k’ represents the kth vehicle [11]. The original feasible solution Food=0,1,2,3,0,4,5,0,6,7 can be expressed as Food=−1,1,2,3,−2,4,5,−3,6,7, and the path it represents is as follows:Vehicle 1: 0-1-2-3-0Vehicle 2: 0-4-5-0Vehicle 3: 0-6-7-0That is, the sequence from one vehicle number to the next vehicle number is the sequence of collection points that this numbered vehicle passes through.


## 5.2. Population Initialization

The fitness of an individual determines the strengths and weaknesses of the individual and determines whether an individual can be retained in the iterative process. According to the individual’s delivery route sequence chromosome and vehicle sequence chromosome, the delivery task is arranged, and the fitness is calculated. The process is as follows:(1)
For thei−th individual in the population, select an available vehicle according to its vehicle sequence chromosome, and then select as many customer points as possible to be delivered in sequence in its delivery route sequence chromosome. The total demand for customer points should not exceed the rated load of the vehicle.(2)
Judge whether all the customer points in the chromosome of the distribution route sequence have been distributed. If there are customer points to be distributed, return to (1); if not, go to (3).(3)
After completing the task distribution, generate the distribution planJi of the i-th individual in the population, and calculate its total cost Zi according to formula (1).(4)
Take the costZi corresponding to the i-th individual, set fi=1/Zi, and fi is the fitness of the i−th individual.Example: suppose the delivery route sequence chromosome of thet-th individual in the population is [4, 5, 6, 3, 1, 2], and the corresponding customer point demand is [300, 200, 200, 400, 100, 300]; the vehicle sequence chromosome is [2, 3, 1, 4, 5], the corresponding model is [1, 2, 2, 3, 3], and the corresponding rated load of the model is [300, 500, 500, 400, 400]; according to the above task allocation method, the assigned tasks are as follows:①
Install vehicles with a sequence number of 2 and model 1, and the service route is 0-4-0②
For vehicles with a sequence number of 3 and model 2, the service route is 0-5-6-0③
For vehicles with a sequence number of 1 and model 2, the service route is 0-3-1-0④
For vehicles with a sequence number of 4 and model 3, the service route is 0-2-0⑤
For other vehicles, distribution tasks are not assignedThen, the total costZt and the fitness degree ft=1/Zt are calculated according to the assigned task and formula (1).


## 5.3. Crossover Operation

Since the variable-point crossing may cause the vehicle to be overloaded, resulting in an illegal solution, this paper adopts a fixed-point single-point crossing, and the crossing point is set after the first gene (vehicle gene). Individuals A and B are randomly selected according to the crossover probabilityPc, and the specific steps for performing crossover operations on them are as follows:(1)
Randomly generate a natural number between 1 andH, representing the same chromosome number of the two individuals to be crossed (the number of individual A is set to a, the number of individual B is set to b, and a = b).(2)
Take out the customer genes with the same two chromosomesa and b, and store them in the gene bank Fa,Fb.(3)
Exchange the customer genes of 2 chromosomes (keep the order of customer genes unchanged).(4)
Compare the client genes of chromosomes other than chromosomea in individual A with the genes of Fb one by one, and delete all the same genes. Similarly, perform similar operations on individual B.(5)
Insert the genes inFa into any position after the first gene of any chromosome of individual A randomly one by one. After that, judge whether the vehicle is overloaded; if it is overloaded, randomly insert the next chromosome, and judge whether it is overloaded again, and so on, until all the genes in Fa are allocated. Perform similar operations on individual B.


## 5.4. Mutation Operation

Suppose the mutation probabilityPe, the first gene of each chromosome of an individual does not generate mutation, and for each other gene i, a floating-point number ri corresponding to gene i is randomly generated between 0 and 1. If ri<Pe, put the gene into the mutation gene bank G, and delete it from the chromosome at the same time; otherwise, this gene will not produce mutation. After that, follow the above step (5) to randomly insert the genes in G into the chromosomes one by one.


## 5.5. Selection Operation

The traditional proportional selection method (the probability of selection is proportional to the fitness of the individual) has some bad properties: in the early stages of iterations, some super individuals with high fitness will dominate the selection process, resulting in excessive selection pressure; in the late stage, the fitness gap between individuals is small, resulting in too little selection pressure. The normalization technique proposed by CHENG and others for the problem of et al. minimization makes up for the above shortcomings, and its form is as follows:(16)fk′=fmax−fk+γfmax−fmin+γ,where fk is the fitness of the individual; fmax is the maximum fitness of the population individual; fmin is the minimum fitness of the population individual; γ is the average fixed cost of the vehicle; and fk′ is the fitness after transformation.The advantage of convertingfk into fk′ is that the survival pressure is always at a relatively moderate position, thereby preventing premature convergence. Then, use roulette to choose: first, calculate the total fitness F=∑fki′; second, calculate the relative probability of individual i, Pri=fki′/F; then, calculate the cumulative probability of individual i, Pei=∑Prjj=1,2,…,i; finally, randomly generate a floating-point number ri in the interval 0 ∼ 1; if ri<Pei, select the first individual; otherwise, choose to make Pei−1<ri≤Pei hold the i-th individual.


## 5.6. Elite Selection

TheS + 1th individual is designed to be initially used to preserve the optimal individual in the initial population. After that, if the fitness of the S + 1th individual is due to all offspring individuals, it is used to replace the worst individual in the offspring; otherwise, it is replaced by the best individual in the offspring. On the one hand, elite selection can ensure that the genes of outstanding individuals are not lost in the process of evolutionary selection, thereby accelerating convergence; on the other hand, it ensures that the optimal individual in the offspring population will not be worse than the parent population, thus making the evolutionary curve monotonously decreasing.


## 6. Example Simulation and Analysis

In order to verify the effectiveness of the algorithm, 19 recovery points and 1 recovery center are selected. The calculation example is compared with the traditional genetic algorithm on MATLAB 2018a to verify the effectiveness and feasibility of the proposed multichromosome genetic algorithm under the model. The running environment of the experiment is AMD Ryzen 53550H with Radeon Vega Mobile Gfx 2.10 GHz CPU 16 GB memory, Windows 10 64-bit operating system.


### 6.1. Simulation

In the experiment, there are two different types of recovered vehicles, and the rated load of each type of recovered vehiclesQm is 6 t and 8 t; the fixed cost C1m (yuan) is 40 and 60; the unit transportation cost C2m (yuan) is 5, 7, and 8; the constant speed of the vehicle (km/h) is 40; and the penalty cost (yuan/min) for late arrival is 4. See Table 1 for other parameters of recycling companies and recycling points, and the parameter values in the model are shown in Table 1.Table 1
Recycling center and recycling point parameter table.
Customer numberRecycling amount (ton)CoordinateTime window00(0, 0)[0, 0]12.53(3, 2)[0, 10]21.22(1, 5)[10, 35]31.65(5, 4)[5, 25]41.42(4, 7)[0, 5]50.85(0, 8)[15, 30]61.36(3, 11)[35, 75]72.20(7, 9)[40, 75]83.31(9, 6)[25, 45]91.46(10, 2)[5, 25]101.89(14, 0)[65, 85]112.35(2, 16)[35, 50]123.80(6, 18)[20, 35]131.75(11, 17)[48, 75]143.91(15, 12)[10, 30]151.43(19, 9)[70, 90]162.82(22, 5)[0, 20]175.83(21, 0)[55, 74]181.34(27，9)[0，20]191.67(15, 19)[60, 85]


### 6.2. Path Optimization Results and Algorithm Comparison

According to the algorithm design and solving steps in Section2, it is solved by an improved genetic algorithm. Improved GA solving parameters: the population size is 1000, the number of solutions is 500, the dimension D is 96, the mutation rate is 0.01, and the number of iterations is 500. The program was run 20 times, the running time was 61.1196 seconds, and the minimum objective function was 987.2. The optimal recovery path is shown in Table 2, and the path diagram is shown in Figure 2.Table 2
Recycling path of vehicles in the recycling center.
Vehicle numberModel (t)Recovery path180-8-9-1-0260-7-4-3-2-6-0360-5-11-12-0460-13-19-0560-15-10-0660-17-16-14-0760-18-0Figure 2
Recycling path diagram of recycling companies.Comparing GA and the improved GA for 500 iterations, it can be seen from Figure3 that, in the process of algorithm iteration, the gap between the objective function values obtained by IGA and GA is increasing. The stage is improved, and the minimum value of the IGA function in the iterative process is significantly reduced, indicating that the improved strategy for the honeybee stage in this article is effective. At the same time, as the number of algorithm iterations increases, it is obvious from Figure 3 that GA has reached the optimal value . It can be seen that‐ when the number of iterations reaches about 70 times, GA reaches the optimal value, and the objective function value of the IGA solution is still significantly reduced. This further shows that the search mechanism in this article can expand the search range of borrowing and improve the optimization speed of the solution and accuracy, and the improved genetic algorithm has higher quality, which verifies the effectiveness of the algorithm in solving the model.Figure 3
Comparison of 20 runs of IGA and GA.


### 6.3. Comparative Analysis of Different Models

From Table3, it can be seen that the total cost of recycling a single 6 t vehicle is 2.1140×103 yuan, the total cost of recycling a single 8 t vehicle is 2.5417×103 yuan, and the total cost of recycling 6 t and 8 t multiple models is 1.0604×103 yuan. It is concluded that the total transportation cost of recycling for multiple vehicles is significantly lower than the total cost of recycling for a single vehicle. From this, it is concluded that the use of multiple models can better reduce the total cost of recovery.Table 3
Comparison of the total cost of recovery between a single model and multiple models.
ModelTotal cost recovery6 t1203.88 t1173.56 t and 8 t987.2


## 6.1. Simulation

In the experiment, there are two different types of recovered vehicles, and the rated load of each type of recovered vehiclesQm is 6 t and 8 t; the fixed cost C1m (yuan) is 40 and 60; the unit transportation cost C2m (yuan) is 5, 7, and 8; the constant speed of the vehicle (km/h) is 40; and the penalty cost (yuan/min) for late arrival is 4. See Table 1 for other parameters of recycling companies and recycling points, and the parameter values in the model are shown in Table 1.Table 1
Recycling center and recycling point parameter table.
Customer numberRecycling amount (ton)CoordinateTime window00(0, 0)[0, 0]12.53(3, 2)[0, 10]21.22(1, 5)[10, 35]31.65(5, 4)[5, 25]41.42(4, 7)[0, 5]50.85(0, 8)[15, 30]61.36(3, 11)[35, 75]72.20(7, 9)[40, 75]83.31(9, 6)[25, 45]91.46(10, 2)[5, 25]101.89(14, 0)[65, 85]112.35(2, 16)[35, 50]123.80(6, 18)[20, 35]131.75(11, 17)[48, 75]143.91(15, 12)[10, 30]151.43(19, 9)[70, 90]162.82(22, 5)[0, 20]175.83(21, 0)[55, 74]181.34(27，9)[0，20]191.67(15, 19)[60, 85]


## 6.2. Path Optimization Results and Algorithm Comparison

According to the algorithm design and solving steps in Section2, it is solved by an improved genetic algorithm. Improved GA solving parameters: the population size is 1000, the number of solutions is 500, the dimension D is 96, the mutation rate is 0.01, and the number of iterations is 500. The program was run 20 times, the running time was 61.1196 seconds, and the minimum objective function was 987.2. The optimal recovery path is shown in Table 2, and the path diagram is shown in Figure 2.Table 2
Recycling path of vehicles in the recycling center.
Vehicle numberModel (t)Recovery path180-8-9-1-0260-7-4-3-2-6-0360-5-11-12-0460-13-19-0560-15-10-0660-17-16-14-0760-18-0Figure 2
Recycling path diagram of recycling companies.Comparing GA and the improved GA for 500 iterations, it can be seen from Figure3 that, in the process of algorithm iteration, the gap between the objective function values obtained by IGA and GA is increasing. The stage is improved, and the minimum value of the IGA function in the iterative process is significantly reduced, indicating that the improved strategy for the honeybee stage in this article is effective. At the same time, as the number of algorithm iterations increases, it is obvious from Figure 3 that GA has reached the optimal value . It can be seen that‐ when the number of iterations reaches about 70 times, GA reaches the optimal value, and the objective function value of the IGA solution is still significantly reduced. This further shows that the search mechanism in this article can expand the search range of borrowing and improve the optimization speed of the solution and accuracy, and the improved genetic algorithm has higher quality, which verifies the effectiveness of the algorithm in solving the model.Figure 3
Comparison of 20 runs of IGA and GA.


## 6.3. Comparative Analysis of Different Models

From Table3, it can be seen that the total cost of recycling a single 6 t vehicle is 2.1140×103 yuan, the total cost of recycling a single 8 t vehicle is 2.5417×103 yuan, and the total cost of recycling 6 t and 8 t multiple models is 1.0604×103 yuan. It is concluded that the total transportation cost of recycling for multiple vehicles is significantly lower than the total cost of recycling for a single vehicle. From this, it is concluded that the use of multiple models can better reduce the total cost of recovery.Table 3
Comparison of the total cost of recovery between a single model and multiple models.
ModelTotal cost recovery6 t1203.88 t1173.56 t and 8 t987.2


## 7. Conclusions

This paper considers the multivehicle reverse logistics path under time constraints to conduct research, and the main conclusions are as follows:(1)
According to the characteristics of recycled products and the requirements of low‐carbon green logistics, the four aspects of fixed costs, transportation costs, carbon emissions, and time penalty costs are comprehensively considered. A path optimization model is established in which the recycling center carries out recycling from multiple recycling points with the goal of minimizing the total cost of recycling.(2)
Taking into account the shortcomings of early maturity of genetic algorithms and fast convergence in the later stages of evolution, multichromosome genetic algorithms are often used in parking lots. The IGA converges faster than the GA and has better solution results.(3)
The simulation of the calculation example shows that the recycling of multiple-vehicle types is cheaper than recycling of a single-vehicle type, and the efficiency is changed.In the actual reverse logistics operation environment, the complexity is far greater than the ideal state in the article. In the subsequent research of the article, the quality uncertainty problem can be considered together, which is closer to the actual reverse logistics environment.



---

*Source: 5559684-2021-04-13.xml*