Location-Routing Optimization with Renting Social Vehicles in a Two-Stage E-Waste Recycling Network

Abstract

E-waste recycling has been a hot topic in recent years. The low efficiency and high-operation cost of recycling make it more important to build perfect e-waste recycling networks. To hedge against the limitation of vehicle resources being often neglected in existing research, we propose a mixed integer linear programming model of e-waste recycling by renting idle social vehicles. In the model, both decisions made on the location selection of recycling sites and vehicle routings satisfying all of the demand nodes over the network within time windows are required to minimize the total operating cost. An improved genetic algorithm and heuristic algorithm are designed to solve the model, and numerical experiments are produced to demonstrate the effectiveness of the proposed model and algorithms.

1. Introduction

With the development of sharing economies and the advent of the “Internet +” wave, enterprises are constantly innovating new forms to figure out traditional pain points of various industries. Sharing economies can create social value and can improve the lives of people all over the world.

The shortened electrical and electronic product life-cycles, along with the rapid technological innovation and increased need of automated production, have made e-waste one of the fastest-growing waste streams. The recycling of e-waste is related to environment and resources. On one hand, e-waste is called urban minerals because of a large amount of high-value metals such as gold and copper [1]. On the other hand, it contains harmful substances that affect human health and damage ecological environment. How to recycle e-waste in a better way has always been a problem perplexing the industries and the markets.

There are three fundamental weaknesses of current e-waste recycling. First, the distances between demand nodes and recycling sites so far make it such that users with recycling demands are unwilling to discard e-waste to recycling sites by themselves. Second, if recycling sites arrange vehicles to pick up e-waste door to door, it is unlikely that vehicles can arrive at all of the demand nodes within their respective service time windows. Third, in the recycling sites, there are a limited number of owned vehicles that may not be able to satisfy recycling demands in time. On the other hand, it is uneconomic to equip more vehicles to satisfy peak demands.

In China, sharing models such as car sharing and bicycle sharing are prevalent. In metropolitan areas, there is a considerable degree of inefficiency in transporting trucks due to traffic congestion, etc., and small and medium-sized trucks that transport in urban areas, which are usually empty on the return trip. There are already companies in the business of leasing trucks at hourly rates. Thompson et al. [2] investigated the potential of shared networks for general freight transportation in urban areas in Melbourne to reduce congestion and to lower transportation costs, and the results show that sharing freight makes it possible to reduce transportation costs significantly.

This study makes decisions on the selection of recycling sites for constructing efficient e-waste recycling network, the selection of outsourcing demands to be satisfied by social vehicles, and vehicle routing solutions for the remaining demands, aiming to minimize the sum of the total rental cost and the total transportation cost in the recycling network. With the assumption of customer perferred time windows of service, selecting outsourcing demands has a great impact on the routing scheduling for the remaining demands to be completed by owned vehicles. The two choices of completing recycling demands, i.e., using social or owned vehicles, makes the problem decision more complicated. A full solution consists of deciding the locations of recycling sites, the selection of outsourcing demands, and making a vehicle routings schedule for the remaining demands in the e-waste recycling network. Note that selecting social vehicles causes some amount of renting fee. To minimize the total rental cost and the total transportation cost, the selection of which and how many demands to be served by social vehicles are closely related to the total capacity of vehicles and the preferred service time windows of customer demands.

The main contributions of this work are as follows:

• Under the background of sharing economy, we introduce the application of social vehicles with rental cost into the classical integrated recycling cite location and vehicle routing problem in an e-waste recycling network. There are two stages of e-waste collection, where in the first stage, e-waste recycling demands are processed by either self-delivery or door-to-door pickup and, in the second stage, the collected e-wastes are delivered to the unique processing centre.
• An MILP model is established, in which it is assumed that different recycling sites are equipped with an unequal number of vehicles, and each vehicle shall depart from and return to its respective recycling site in the first collection stage.
• An improved genetic algorithm and a two-stage cyclic optimization-based heuristic algorithm are developed to solve the considered problem.

The rest of this paper is organized as follows. Section 2 reviews the relevant papers in the literature. In Section 3, the problem is stated and formulated. Next, a genetic and a two-stage greedy algorithm are proposed to solve the MILP model in Section 4. Section 5 reports computational experiments. Finally, the paper is concluded in Section 6.

2. Literature Review

In recent years, e-waste has become a global issue because of the quick maturation of electronics, low recycling rate in some cases, utilization of raw materials, and pollution effects around the globe [3,4]. Therefore, the recycling of e-waste has attracted the attention of domestic and foreign enterprises and scholars. This section mainly reviews the current research situation of e-waste recycling and the location-routing problem (LRP).

Guo et al. [5] raised the fact that there are many problems in the process of e-waste recycling such as high economic cost, environmental detriment caused by improper recycling, ignorance of social benefits of recycling, uncertain recycling amounts, and single recycling channels. He et al. [6] compared soil pollution caused by heavy metals from traditional industrial operations and e-waste recycling activities in the Pearl River Delta. They conclude that, in view of the short development of e-waste recycling and the fact that it is largely unregulated, cracking down on illegal e-waste recycling and strengthening pollution control of related activities are very significant. Li et al. [1] describe the threat to environment and human health caused by hazardous substances in e-waste all over China as well as the management status and problems of e-waste management. At last, they put forward controllable sources of pollution, and eco-friendly and efficient remediation technologies to solve the problem of e-waste in China. Cao et al. [7] proposed a hierarchical heuristic algorithm based on tabu search for the LRP problem of bio-fuel cell enterprises and verified the effectiveness and high efficiency of the algorithm. Gamberini et al. [8] aimed to optimize the e-waste recycling network according to technical and environmental performance criteria in a real case study from Eggio Emilia in northern Italy. They developed simulation models to measure the performance of each feasible solution. Nowakowski [9] solved the WEEE storage and transportation i.e., vehicle loading problem and vehicle routing problem for a Polish e-waste recycling company, aiming at maximizing the vehicle loading rate. He developed adaptive heuristic algorithms to solve the proposed problem. Beneventtiet et al. [10] designed a multi-product maximum–minimum-waste LRP model, taking into account the different impacts of waste on people, with the goal of maximizing the minimum weighted distance between facilities and vulnerable people stations as well as transportation routes while minimizing the total harm and cost to non-vulnerable people. Sakti et al. [11], in order to minimize the total cost in a waste network in Yogyakarta, Indonesia, built a model of the location-routing problem considering two types of fleets. Finally, a greedy algorithm is designed to solve the large-scale arithmetic cases.

Zhao et al. [12] analyzed the situation of incorporating inventory risk into explosive waste management. They developed a dual-objective model to minimize total cost and total risk at the same time and investigated some numerical experiments using real data in China. Dukkanci et al. [13] developed a mixed integer programming formula for GLRP and described preprocessing rules and valid equations to enforce the formula. Different-sized instances are solved by two heuristic algorithms designed. In order to solving the Last Mile distribution for online shopping, Dukkanci et al. [14] proposed a novel location-routing problem with two kinds of service options that denote home delivery and pickup. They designed a hybrid heuristic combining GA and LS to prove that setting a reasonable scope of customer’s acceptable distances and an optimal distance for a certain distribution system can decrease operation costs. Ng et al. [15] introduced the multi-depot open LRP with a heterogeneous fixed fleet in which raw materials from different suppliers coordinating several carriers are delivered to a single delivery point. The problem was modeled to minimize the total cost, selecting the carriers to be contracted, the vehicles to be used from each contracted carrier, and the collection routes. An intelligent meta-heuristic which incorporates problem-specific knowledge is proposed to handle this problem. A new two-phase deterministic mixed-integer linear programming model is proposed to deal with the inherent uncertainty of input data in the location and vehicle routing scheduling problems in cross-docking distribution networks by Vandani et al. [16]. Moreover, a meta-heuristic algorithm was designed, and various computational tests were used to demonstrate the applicability and capability of the proposed robust two-phase model and meta-heuristic solution approach. Kuroki et al. [17] made decisions about the timing and location of the installation of recycling facilities by considering regional characteristics. A simulated annealing algorithm was designed to solve the model by evaluating the recycling and transportation costs based on the future demand for rare metals in Japan. A trade-off between profit-oriented and service-oriented collector behavior management models was proposed for an e-waste recycling logistics network that considers both on-call and door-to-door demand, and the proposed model was solved using Tabu Search by Pourhejazy et al. [18].

Abid et al. [19] conducted a literature review based on more than 50 reviewed articles on simulation techniques in the context of reverse logistics. They conclude that discrete event simulation and system dynamic are the most flexible and widely used tools. Agnusdei et al. also endorsed this conclusion in [20]; in addition, they reviewed that various methods have been applied (e.g., mixed integer linear and nonlinear models, multi-objective models, fuzzy linear programming models, etc.), of which 73% of the cases are deterministic models, but 19% of stochastic programming models have also been found.

We summarize some existing related research in

Table 1. Comparison of research in the location routing problem.

References	Objective	Vehicle Fleet	Vehicle Capacity	Time Window	Solution Method
Cao et al. [7]	min FEC & TC	single	-	-	CPLEX,TS
Nowakowski [9]	min TC	single	✓	-	GLSA
Zhao et al. [12]	min TC, FEC & risk	single	✓	-	TOPSIS
Beneventtiet et al. [10]	max MWD; min THIP, FEC & TC	single	-	-	CPLEX
Dukkanci et al. [13]	min FEC, FC & ${\mathrm{CO}}_2$ C	single	-	✓	ILSA
Zhou et al. [14]	min FEC, TC & SDC	single	✓	✓	HESA
Ng et al. [15]	min TC	single	✓	-	MA
Vandani et al. [16]	min TC & IC	multi	✓	✓	MA
Kuroki et al. [17]	min RC & TC	single	-	-	SAA
Pourhejazy et al. [18]	max TP	single	✓	✓	TS
this study	min FC & RSVC	multi	✓	✓	CPLEX, GA, HA

Note: TC: transportation cost; FEC: facility establishment cost; RC: recycling cost; MWD: the minimum weighted distance; THIP: the total hazardimposed on the non-vulnerable population; FC and CO${}_2$ C: fuel and CO${}_2$ emissions cost; SDC: the second delivery cost; IC: inventory cost; RSVC: renting social vehicles cost; TP: total profit; TS: Tabu search; GA: genetic algorithm; MA: metaheuristic algorithm; HA: heuristic algorithm; HESA: hybrid evolution search algorithm; ILSA: iterated local search algorithm; GLSA: greedy and local search algorithm; SAA: simulated annealing algorithm.

; it can be concluded that, though there have been abundant researches on e-waste recycling combined with location-routing problems, most existing research considers that vehicles are sufficient and single categories while we focus on the limited number of owned vehicles. At the same time, we consider renting social idle vehicles in an e-waste recycling network when e-waste recycling demands surge, which is also a gap in existing related research.

3. Model Formulation

This section first describes the problem under consideration together with basic assumptions and notations. We then present a mixed integer linear programming model.

3.1. Problem Description

Figure 1 illustrates an e-waste recycling network in which there are four demand nodes, two candidate recycling sites each are equipped with one owned vehicle, and the single processing centre. Recycle site 1 other than recycle site 2 is selected for satisfying the recycling demands. For the first stage delivery, the last demand node (i.e., node 4) is processed by its own customer at the node, and there are no costs for this pick-up task. For the other three pick-up tasks, nodes 1 and 2 are served by one own vehicle of recycle site 1, and the delivery route is recycling site 1 → demand node 2 → demand node 1 → recycling site 1. Demand node 3 is satisfied by one social vehicle with a pick-up route from demand model 3 → recycling site 1, since its time window cannot be met by the single owned vehicle in time. In the second delivery stage, all of the e-wastes collected by recycling site 1 are transported to the processing centre together (recycling site 1 → processing centre).

Without loss of generality, we consider that, in an e-waste recycling network, there are $\left|N\right|$ demand nodes, $\left|M\right|$ candidate recycling sites, and one processing centre. Moreover, there are two ways of e-waste delivery. One is to deliver the e-waste from demand nodes to recycling sites by customers themselves, and the other way is to deliver e-wastes by recycling site or social vehicles. For the first delivery way, the amount of e-wastes received by one recycling site m is denoted by $w_m$. Therefore, the recycling network only depicts those demand nodes satisfied by the second delivery way. Demand node i has $q_i$ units of e-waste to be recycled, and its processing time is $t_i$. The expected service time window is [$e_i$, $l_i$], where $e_i$ and $l_i$ denote the demand node’s earliest and latest time points of acceptable service, respectively. We select $m_1$ out of the $\left|M\right|$ candidate sites for satisfying the recycling demands. Each recycling site has a finite number of vehicles called own vehicles. On the contrary, the available social vehicles are called outside vehicles.

There are two stages of e-waste collection. In the first stage, the e-waste in the demand nodes are delivered to recycling sites, and in the second stage, the collected e-waste is transported from recycling sites to the processing centre. To differ the transportation tasks in the two stages, we define them as pick-up and transportation tasks, respectively. The owned vehicles in the two stages are of different capacities, i.e., pick-up tasks are served by smaller vehicles and transportation tasks are served by larger vehicles. If pick-up tasks are satisfied by owned vehicles, then it causes transportation costs in accordance with the respective delivery distances. Otherwise, if pick-up tasks are satisfied by social vehicles, then it generally has a higher delivery cost. The problem is to select a subset of recycling sites used for collecting e-waste delivered from demand nodes, to select outsourcing demand nodes to be served by social vehicles, and to decide detailed transportation routes for processing remaining demand nodes by own vehicles, minimizing the total delivery cost of owned and outside vehicles.

3.2. Assumptions

In the considered problem, the following fundamental assumptions are necessary.

• The speed of each vehicle is smooth and uniform in any transportation route. The distance between any two nodes in the recycling network is calculated by Euclidean distance and satisfies the triangle inequality ([21,22]).
• The capacities of recycling sites and the processing centre are infinite ([23]).
• Each own vehicle departures from and returns to its belonging recycling site ([24,25]).
• Rented vehicles and the smaller owned vehicles have the same capacity.
• If a demand node is served by an outside vehicle, the outside vehicle must meet the recycling demand within the time window ([26,27]).
• E-waste of demand nodes that have a pickup service must be picked up at one time by an own vehicle or an outside vehicle. implying that the demand cannot be split and satisfied in two time points ([25,28]).

3.3. Notations

The indices, parameters, and decision variables used in the model are defined as follows:

Indices:

-

i: index of demand node;

-

m: index of recycling site;

-

j: index of demand node and recycling site;

-

p: index of processing centre;

-

v: index of vehicle;

Parameters:

-

$\mathcal{N}$: set of demand nodes, $\mathcal{N}=\{1,2\cdots ,|N\left|\right\}$, where $\left|N\right|$ is the number of demand nodes;

-

$\mathcal{M}$: set of candidate recycling sites, $\mathcal{M}=\left\{\right|N|+1,|N|+2\cdots ,|N|+|M\left|\right\}$, where $\left|M\right|$ is the number of candidate recycling sites;

-

$\mathcal{U}$: set of demand nodes and recycling sites, where $\mathcal{U}=\mathcal{N}\cup \mathcal{M}$;

-

$\mathcal{P}$: set of processing centres;

-

$m_1$: number of recycling sites selected;

-

$b_m^v$: set of own vehicles of each recycling site;

-

$t_{ij}$, $t_{im}$, $t_{mp}$: time between demand node i and demand node j, between demand node i and recycling site m, between recycling site m and processing centre p;

-

$Q_c$: capacity of vehicle which processes pick-up tasks;

-

$Q_t$: capacity of vehicle which processes transportation tasks;

-

$v_c$: uniform speed of any vehicle;

-

$q_i$: amount of e-waste at demand node i;

-

$c_1$, $c_2$: cost of transportation per minute and renting cost per time;

-

$e_i$, $l_i$: the earliest and latest start time acceptable for serving demand node i;

-

$w_m$: amount of self-delivered e-waste received by customers at recycling site m;

-

$t_i$: processing time required by demand node i;

-

$M_1$, $M_2$: two sufficiently large real numbers.

Decision Variables:

-

${\alpha }_i$: equals 1, if e-waste in demand node i is picked up by an outside vehicle, and 0 otherwise;

-

${\alpha }_{im}$: equals 1, if e-waste in demand node i is picked up by an outside vehicle to recycling site m, and 0 otherwise;

-

$x_{ij}$: equals 1, if an own vehicle travels from node i to node j, and 0 otherwise;

-

$y_m$: equals 1, if candidate recycling site m is selected, and 0 otherwise;

-

$x_{imv}$: equals 1, if e-waste in demand node i is picked up by own vehicle v of recycling site m, and 0 otherwise;

-

${\theta }_{imv}$: equals 1, if an own vehicle v of recycling site m travels form recycling site m to demand node i, and 0 otherwise;

-

${\gamma }_{imv}$: equals 1, if an own vehicle v of recycling site m travels form demand node i to recycling site m, and 0 otherwise.

-

${\delta }_{im}$: equals 1, if e-waste in demand node i is picked up by an own vehicle of recycling site m, and 0 otherwise;

-

$T_i$: arrival time of a vehicle in demand node i;

-

$s_{mv}$: departure time of an own vehicle v in recycling site m.

-

${\beta }_i$: an intermediate variable, equals 1 if $T_i\ge e_i$, and 0 otherwise.

3.4. Mathematical Model

Based on the above parameters and variables, the following mathematical model is established for the considered problem.

There are generic models about the location-routing problem in the literature, mainly including flow constraints ([11,25]), capacity constraints ([25,29]), time window constraints, and constraints about the maximum number of sites ([30]). In this study, while constructing the MILP model, it benefits from them. Moreover, the model used in the study differs from the existing studies by taking into account owned vehicle departures from their own recycling sites rather than all vehicle departures from one depot ([31]). Moreover, demand nodes served by rented outside vehicles can only be transported to recycling sites selected.

The objective is to minimize the total costs that contain three parts. The first part is that, when e-waste of the demand nodes is collected by outside vehicles, it generates the outsourcing cost $C_1$, which is composed of fixed cost of rented social vehicles and transportation cost of the vehicles:

$$C_1=\sum _{i\in \mathcal{N}}{\alpha }_i·c_2+\sum _{i\in \mathcal{N}}\sum _{m\in \mathcal{M}}{\alpha }_{im}·t_{im}·v_c·c_1$$

(1)

The second part is the transportation cost $C_2$ between the recycling site m and the demand node i, the demand node i and the demand node j, and the demand node i and the recycling site m when the recycling site’s own vehicles serve the demand nodes:

$$\begin{array}{c}\hfill C_2=\sum _{i\in \mathcal{N}}\sum _{j\ne i\in \mathcal{N}}{x}_{ij}·t_{ij}·v_c·c_1\\ \hfill +\sum _{i\in \mathcal{N}}\sum _{m\in \mathcal{M}}\sum _{v\in b_{mv}}{\theta }_{imv}·t_{mi}·v_c·c_1\\ \hfill +\sum _{i\in \mathcal{N}}\sum _{m\in \mathcal{M}}\sum _{v\in b_{mv}}{\gamma }_{imv}·t_{im}·v_c·c_1\end{array}$$

(2)

The third part is the transportation cost $C_3$ caused by transporting e-waste, which is picked up by vehicles and sent to recycling sites by customers from the recycling site m to the recycling centre p:

$$C_3=\sum _{m\in \mathcal{M}}⌈\frac{y_m·{\omega }_m+{\sum }_{i\in \mathcal{N}}({\delta }_{im}+{\alpha }_{im})·q_i}{Q_t}⌉·t_{mp}·v_c·c_1$$

(3)

The objective function can thereby be formulated as follows:

$$minW=C_1+C_2+C_3$$

(4)

Constraints (5) and (6) indicate that the candidate recycling site is selected only when the e-waste of demand nodes is transported to the recycling site m by its own vehicle.

$${\delta }_{im}\le y_m\forall i\in \mathcal{N},m\in \mathcal{M}$$

(5)

$$\sum _{i\in \mathcal{N}}{\delta }_{im}\ge y_m\forall m\in \mathcal{M}$$

(6)

Constraints (7) and (8) ensure that the rented social vehicle may only transport e-waste to the recycling site selected.

$$\sum _{m\in \mathcal{M}}{\alpha }_{im}={\alpha }_i\forall i\in \mathcal{N}$$

(7)

$${\alpha }_{im}\le y_m\forall i\in \mathcal{N},\forall m\in \mathcal{M}$$

(8)

Constraint (9) indicates that the e-waste in a demand node is either picked up by an own vehicle or a rented outside vehicle.

$$\sum _{m\in \mathcal{M}}{\delta }_{im}+\sum _{m\in \mathcal{M}}{\alpha }_{im}=1\forall i\in \mathcal{N}$$

(9)

Constraint (10) indicates that the number of recycling sites selected is up to $m_1$.

$$\sum _{m\in \mathcal{M}}{y}_m<=m_1$$

(10)

Constraints (11) and (12) ensure that there is only one vehicle entering and leaving each demand node.

$$\sum _{j\in \mathcal{U},j\ne i}{x}_{ji}+{\alpha }_i=1\forall i\in \mathcal{N}$$

(11)

$$\sum _{j\in \mathcal{U},j\ne i}{x}_{ij}+{\alpha }_i=1\forall i\in \mathcal{N}$$

(12)

Constraint (13) indicates that e-waste in demand node is picked up by one and only one vehicle.

$$\sum _{m\in \mathcal{M}}\sum _{v\in b_m^v}{x}_{imv}+{\alpha }_i=1\forall i\in \mathcal{N}$$

(13)

Constraint (14) ensures that the e-waste picked up by one vehicle is within the capacity of the vehicle.

$$\sum _{i\in \mathcal{N}}{x}_{imv}·q_i\le Q_c\forall m\in \mathcal{M},\forall v\in b_m^v$$

(14)

Constraints (15)–(17) indicate the relationship between the order of demand node i and j that are picked up by the same vehicle.

$$x_{ij}\le M\left(1-x_{imv}\right)+M_2·x_{jmv}\forall i,j\in \mathcal{N},j\ne i,\forall m\in \mathcal{M},\forall v\in b_m^v$$

(15)

$$x_{ij}+x_{ji}\le 1\forall i,j\in \mathcal{N},j\ne i$$

(16)

$$x_{ij}\le (2-{\alpha }_i-{\alpha }_j)/2\forall i,j\in \mathcal{N},j\ne i$$

(17)

Constraint (18) indicates that the e-waste of the demand node only needs an own vehicle to pick up at most.

$$\sum _{v\in b_m^v}{x}_{imv}={\delta }_{im}\forall i\in \mathcal{N},\forall m\in \mathcal{M}$$

(18)

Constraints (19)–(23) indicate the relevant constraints of the first demand node, which is picked up by an own vehicle.

$$M·\sum _{i\in \mathcal{N}}{\theta }_{imv}\ge \sum _{i\in \mathcal{N}}{x}_{imv}\forall m\in \mathcal{M},\forall v\in b_m^v$$

(19)

$${\theta }_{imv}\le x_{imv}\forall i\in \mathcal{N},\forall m\in \mathcal{M},\forall v\in b_m^v$$

(20)

$$\sum _{i\in \mathcal{N}}{\theta }_{imv}\le 1\forall m\in \mathcal{M},\forall v\in b_m^v$$

(21)

$${\theta }_{imv}\le \sum _{j=N+1}^U{x}_{ji}\forall i\in \mathcal{N},\forall m\in \mathcal{M},\forall v\in b_m^v$$

(22)

$$x_{mi}\le {\delta }_{im}\forall i\in \mathcal{N},\forall m\in \mathcal{M}$$

(23)

Constraints (24)–(28) indicate the relevant requirements of the last demand node that is picked up by an own vehicle.

$$M·\sum _{i\in \mathcal{N}}{\gamma }_{imv}\ge \sum _{i\in \mathcal{N}}{x}_{imv}\forall m\in \mathcal{M},\forall v\in b_m^v$$

(24)

$${\gamma }_{imv}\le x_{imv}\forall i\in \mathcal{N},\forall m\in \mathcal{M},\forall v\in b_m^v$$

(25)

$$\sum _{i\in \mathcal{N}}{\gamma }_{imv}\le 1\forall m\in \mathcal{M},\forall v\in b_m^v$$

(26)

$${\gamma }_{imv}\le \sum _{j=N+1}^U{x}_{ij}\forall i\in \mathcal{N},\forall m\in \mathcal{M},\forall v\in b_m^v$$

(27)

$$x_{im}\le {\delta }_{im}\forall i\in \mathcal{N},\forall m\in \mathcal{M}$$

(28)

Constraint (29) indicates that each own vehicle of a recycling site serves at most one routing.

$$\sum _{i\in \mathcal{N}}{x}_{mi}=\sum _{i\in \mathcal{N}}{x}_{im}\le b_m^v\forall m\in \mathcal{M}$$

(29)

Constraints (30)–(35) indicate the time relationship demand node between i and j that are picked up by the same vehicle.

$$T_i\ge e_i-M\left(1-{\beta }_i\right)\forall i\in \mathcal{N}$$

(30)

$$T_i\le e_i+M{\beta }_i\forall i\in \mathcal{N}$$

(31)

$$T_j\ge T_i+t_i+t_{ij}-M\left(2-x_{ij}-{\beta }_i\right)\forall i,j\in \mathcal{N},j\ne i$$

(32)

$$T_j\le T_i+t_i+t_{ij}+M\left(2-x_{ij}-{\beta }_i\right)\forall i,j\in \mathcal{N},j\ne i$$

(33)

$$T_j\ge e_i+t_i+t_{ij}-M\left(1-x_{ij}+{\beta }_i\right)\forall i,j\in \mathcal{N},j\ne i$$

(34)

$$T_j\le e_i+t_i+t_{ij}+M\left(1-x_{ij}+{\beta }_i\right)\forall i,j\in \mathcal{N},j\ne i$$

(35)

Constraints (36)–(38) indicate the time window requirements for the vehicle to arrive at the demand node.

$$T_i\le s_{mv}+t_{mi}+M(1-{\theta }_{imv})\forall i\in \mathcal{N},\forall m\in \mathcal{M},\forall v\in b_m^v$$

(36)

$$T_i\ge s_{mv}+t_{mi}-M(1-{\theta }_{imv})\forall i\in \mathcal{N},\forall m\in \mathcal{M},\forall v\in b_m^v$$

(37)

$$T_i\le l_i\forall i\in \mathcal{N}$$

(38)

Constraint (39) is the range of starting time of each own vehicle.

$$s_{mv}\ge 0\forall m\in \mathcal{M},\forall v\in b_m^v$$

(39)

Finally, constraints (40) and (41) give the range of binary variables.

$${\alpha }_i,{\beta }_i,{\alpha }_{im},x_{ij},y_m,{\delta }_{im}\in \{0,1\}\forall i\in \mathcal{N},j\in \mathcal{N},j\ne i,m\in \mathcal{M}$$

(40)

$$x_{imv},{\theta }_{imv},{\gamma }_{imv}\in \{0,1\}\forall i\in \mathcal{N},m\in \mathcal{M},v\in b_{mv}$$

(41)

4. Solutions

4.1. Genetic Algorithm

The genetic algorithm is one of the algorithms that simulate a natural evolution process to search for nearly optimal solutions ([32,33]).The general steps of the algorithm are as follows: (i) generate initial population, in which each individual is called a chromosome; (ii) iterative optimization, in which in each iteration, the population undergoes several genetic operations, namely selection operation, crossover operation, and mutation operation, to complete the evolutionary process of the population. In addition, infeasible solutions may be generated in the process of iteration. In this paper, the objective value of an individual violating the rules of chromosome generation is specified to be arbitrarily large, so that the individual is discarded during the process of iteration. The specific steps of the algorithm are depicted as follows.

4.1.1. Chromosome Coding

The encoding method of chromosome is integer encoding, and the number of genes on chromosome is $2\left|N\right|$, where $\left|N\right|$ is the number of demand nodes. Gene i (i ∈ $[1,N]$) denotes the number of demand node, gene N + i (i ∈ $[1,N]$) denotes the number of vehicle corresponding to the gene i. If $\left|N\right|$ = 10, $\left|M\right|$ = 3, $|m_1|$ = 2, and the number of own vehicles is 2; then, ${\sum }_{m\in M}{b}_{mv}^m=6$. The number of vehicles is $1\sim 6$, where $1\sim b_{mv}^1$ is the number of vehicles in recycling site 1, $b_{mv}^1+1\sim b_{mv}^1+b_{mv}^2$ is the number of vehicles in recycling site 2, etc. When there is no owned vehicle serving demand node i, the code of gene N + i is ‘recycling site number + outside vehicle number’, where the outside vehicle number is set to $se{t}_{ov}$. Figure 2 illustrates a feasible chromosome.

The chromosome indicates that owned vehicle 1 travels from demand node 1 to demand node 5, owned vehicle 2 travels from demand node 2 to demand node 3, etc. Outside vehicle 01 travels from demand node 10 to recycling site 2.

4.1.2. Population Initialization

We first present two rules on the pick-up task processing sequence.

$Rule\left(i\right)$: The sequence of genes in the first half of the chromosome is generated by sorting the demand nodes from small to large according to the right time window $l_i$. If the right time windows of two demand nodes are equal, then the sequence is sorted from small to large according to the left time window $e_i$. If the left and right time windows of the two demand nodes are equal, they are sorted randomly.

$Rule\left(ii\right)$: The sequence of genes in the first half of chromosome is generated by sorting the demand nodes from small to large according to the right time window $l_i$. If the right time windows of two demand nodes are equal, then the sequence is sorted from small to large according to the left time window $e_i$. If the left and right time windows of the two demand nodes are equal, they are sorted randomly.

Below are detailed steps for generating the initial population of chromosomes.

$Step$ 1. According to Rule (i), Rule (ii), and the random rule, different probabilities are assigned to generate the first half of the chromosome sequence achieve better quality of the initial solution on the premise of ensuring diversity of the population.

$Step$ 2. For gene N+1, which denotes the number of vehicle corresponding to gene 1, we calculate the time of all vehicles that travel to this gene and then find the vehicle set $kk1$ in which the elements mean that the vehicles can arrive within the time window of this gene.

$Step$ 3. According to the randomly selected recycling sites, the corresponding vehicle set $kk2$ is generated. Find $KK$ = $kk1$ ∩ $kk2$; if $KK$$\ne \varnothing$, gene N + 1 is one of the members in $KK$ randomly. If $KK$ = ∅, gene N + 1 is set by ’recycling site number + outside vehicle number’, where the recycling site number is the one closest to gene N + 1 in the selected recycling sites, and the outside vehicle number is randomly selected in $se{t}_{ov}$.

$Step$ 4. For gene N + i (i ≥ 2) which denotes the number of vehicles corresponding to gene i, first, we judge if vehicle v serves other genes. If vehicle v does not serve any other genes; then, the time of arrival at gene i is the time between the recycling site to which vehicle v belongs and gene i, and the capacity of vehicle v before it arrives is $Q_c$. If vehicle v serves another gene j before i; then, the time of arrival at gene i is $max${$T_j$,$e_j$} + $t_j$ + $t_{ij}$ and the capacity of vehicle v before it arrives at gene i is $Q_c$ − $q_j$. If vehicle v serves two more genes before gene i; then, time of arrival at gene i is $max${$T_{j^{\prime }}$,$e_{j^{\prime }}$} + $t_{j^{\prime }}$ + $t_{i{j}^{\prime }}$, and the capacity of vehicle v before it arrives at gene i is the capacity of vehicle v before it arrives at gene $j^{\prime }$ − $q_{j^{\prime }}$.

$Step$ 5. Find out the vehicle set $kk3$ in which vehicles can meet the capacity constraint and time window constraint of gene i according to $Step$ 4.

$Step$ 6. Find $KK1$ = $kk3$ ∩ $kk2$; if $KK1$$\ne \varnothing$, gene N + i is an arbitrary member in $KK1$ randomly. If $KK1$ = ∅, gene N + i is set by ’recycling site number + outside vehicle number’, where the recycling site number is the one closest to gene N + i in the selected recycling sites, and the number of outside vehicles is randomly selected in $se{t}_{ov}$.

4.1.3. Calculation of Objective Value

We calculate the objective function value according to Formulae (1), (2), and (3) and the following steps.

$Step$ 1. For the sequence of genes in the last half of chromosome, we find out the set $positio{n}_v$, which contains the genes that the owned vehicle v serves. If $positio{n}_v$ contains a single element, then $cost1\left(v\right)=2·v_c·c_1·t_{N+lo{c}_v,positio{n}_v}$. If otherwise, there are two or more elements in $positio{n}_v$, then $h\left(1\right)=v_c·c_1·t_{N+lo{c}_v,positio{n}_v\left(1\right)}$, while $h\left(1\right)$ denotes the transportation cost generated when vehicle v travels to the first element. $h\left(r\right)=h(r-1)+v_c·c_1·t_{positio{n}_v(r-1),positio{n}_v\left(r\right)}$, where $h\left(r\right)$ denotes the transportation cost generated when vehicle v travels to the r element. Therefore, $cost1\left(v\right)=h\left(end\right)+v_c·c_1·t_{positio{n}_v\left(r\right),N+lo{c}_v}$. The transportation cost generated by owned vehicles when they pick up e-waste is $cost11=\sum cost1\left(v\right)$.

$Step$ 2. Find out set $H_{set}$, which contains recycling sites. Outside vehicles travel to these recycling sites. $cost2\left(l\right)=v_c·c_1·t_{H\left(H_{set}\left(l\right)\right),N+H_{set}\left(l\right)}$, where l is the index of $H_{set}$, and thus renting cost $cost22=\sum cost2\left(v\right)+L·c_2$, where L is the number of elements in $H_{set}$.

$Step$ 3. Find out the amount of e-waste that is picked up by owned vehicle v, and then, calculate $Q\left(lo{c}_v\right)$, which denotes the amount of e-waste picked up in the selected recycling site. Find out set $H_{set}$ as in $Step$ 2, and then, update the amount of e-waste of each selected recycling site. Moreover, calculate the total amount of e-waste in each selected recycling site by adding $w_m$, which denotes the amount of self-delivered e-waste by customers. Lastly, calculate the times of transportation from the recycling sites to the processing centre and figure out $cost33$, which represents the transportation cost from recycling sites to the processing centre.

$Step$ 4. Add up the total cost of the recycling network, that is, $total=cost11+cost22+cost33$, and output the final result.

4.1.4. Fitness Function

We use the following function $fit\left(x\right)$ to calculate the fitness value of chromosome x.

$$\begin{array}{c}\hfill fit\left(x\right)=\frac{1}{total\left(x\right)}\end{array}$$

(42)

where $total\left(x\right)$ is the objective value of chromosome x. Obviously, the larger the value of $fit\left(x\right)$, the better the chromosome.

4.1.5. Genetic Operations

In each iteration of $GA$, chromosomes need to perform a series of genetic operations on the population, namely selection, crossover, and mutation. In our algorithm, we apply the roulette method in the selection operation.

A crossover operation refers to selecting two paternal chromosomes first and then applying a single-dot crossover approach, in which two genes from the first half of the paired chromosomes are selected to exchange genes, and the genes in the first half of the gene duplication are changed at last.

A crossover operation is shown in Figure 3. Gene 3 in parent 1 and gene 5 in parent 2 are crossed over; then, this gene is exchanged in offspring 1 and offspring 2. In contrast, gene 1 in offspring 1 and gene 4 in offspring 2 are changed to 2 and 1 in order to avoid duplication.

A mutation operation refers to the mutation of a gene in a chromosome. The mutation rule adopted in this paper is to change some gene N + i of the chromosome, that is, the service vehicle number. The variation range is within the vehicle number range of the selected recycling sites, which are given by the chromosome itself. Figure 4 shows a mutation operation, where gene 14 in parent 1 mutates. In parent 1, recycling sites 1 and 2 are selected, so the value of gene 14 in offspring 1 ranges from 1 to 4. Gene 14 in offspring 1 changes to 4 after a mutation in this instance.

4.1.6. Feasibility Judgment

It is necessary to make a feasibility judgment on whether the offsprings generated after selection, crossover, and mutation operations meet the rules of chromosome generation. The judgment includes two aspects, that is, the capacity constraint of vehicles and the time window constraint.

For the capacity constraint, we first find a set of demand nodes for each vehicle and then sum up the amount of e-waste in these demand nodes. If it exceeds $Q_c$, implying that the offspring is infeasible, then the objective value of the offspring is set to be an infinite real number. The offspring is eliminated in the next iteration.

For the time window constraint, it is necessary to consider owned vehicles of the sites because outside vehicles always meet the time requirement due to the last assumption of the problem. We calculate the vehicle arrival time at each demand node. If the arrival time at any node exceeds its latest acceptable start time, it implies that this offspring is infeasible. Again, the objective value of the offspring is assigned by an infinite real number, and thus, it in eliminated in the next iteration.

4.1.7. Termination Condition

In the $GA$ algorithm, we set two termination conditions: (i) it reaches the maximum iteration times $MAXGEN$, and (ii) the objective value of the current best solution is 0. $GA$ terminates once either condition is met.

4.2. Heuristic Algorithm

In this section, we propose a two-stage greedy algorithm based on clustering to solve the problem effectively. The algorithm divides and the problem into two sub-problems, i.e., the location sub-problem and the routing sub-problem, and solves them iteratively. In each iteration, the output of the location sub-problem serves as the input of the routing sub-problem. The main ideas for solving the two sub-problems are described in the following two subsections.

4.2.1. The Location Sub-Problem

We first calculate the central point coordinate $(x_{ii},y_{ii})$ of all the demand nodes, and it is obtained according to the K-means of Stochastic Gradient Descent ([34]). There are four steps below to obtain the location of central point $(x_{ii},y_{ii})$.

$Step$ 1. Assign initial values to $(x_{ii},y_{ii})$. Calculate the mean value of each dimension of demand node coordinates ($x_i$,$y_i$), and add the random vector to the mean value, which is the initial value of the central point.

$Step$ 2. Calculate the distance between each demand node ($x_i$,$y_i$) and the central point coordinate $(x_{ii},y_{ii})$;

$Step$ 3. Update central point. Select a demand node randomly, and the coordinate of the central point is close to the coordinate of the demand node by $delta=[(x_i,y_i)-(x_{ii},y_{ii})]·eta$, where $eta$ is the learning rate, and the new coordinate of the central point is $(x_{ii},y_{ii})=(x_i,y_i)+delta$;

$Step$ 4. Repeat the above steps. If $delta$ of the current iteration is smaller than that of the previous iteration, stop and output the best solution.

Given the coordinate of central point $(x_{ii},y_{ii})$ and that of each candidate recycling site, the number of vehicles in set $b_m^v$, and the number $m_1$ of selected recycling sites, we calculate $d_{im}$, which denotes the distance between recycling site m and central point i and then sequence the recycling site candidates in the non-decreasing order of $d_m=d_{im}·(1-\frac{b_m^v}{{\sum }_{m\in M}{b}_m^v})$. We then select $m_1$ candidates with the smallest values of $d_m$ to be the final selected recycling sites in the location sub-problem.

4.2.2. The Routing Sub-Problem

$Step$ 1. The set of demand nodes D is sequenced in the non-decreasing order of the latest acceptable start time $l_i$. Ties are broken by selecting the smallest $e_i$, i.e., the earliest acceptable start time.

$Step$ 2. Determine the vehicle for serving each demand node as well as the routing of each vehicle. We first calculate the potentially earliest arrival time $T_{iv}$ at demand node for each vehicle v in the $m_1$ selected recycling sites. With the vehicle capacity constraint and time window requirement of the demand node, the vehicle v with either the smallest $T_{iv}$ or the smallest $|e_i-T_{iv}|$ is selected to actually serve the demand node. If there is no owned vehicle satisfying the above constraint, then the demand node is served by one outside vehicle. Along with the sequence of demand nodes in D (i.e., the sequence obtained in Step 1), the corresponding service vehicle index sequence can be produced. If the measure of smallest $T_{iv}$ is adopted, then the obtained vehicle index sequence is denoted by $V_1$; otherwise, if the measure of smallest $|e_i-T_{iv}|$ is used, then it is denoted by $V_2$.

$Step$ 3. Compare the total cost of the solution obtained by sequence $V_1$ and that by sequence $V_2$ in the routing sub-problem, and select the sequence with the smaller cost for the solution of the service vehicle routing sub-problem.

5. Computational Experiments

In the numerical experiments, MATLAB2014b is used on the personal computer with Intel (R) Core (TM) i5-8500T CPU @ 2.11GHz, and Windows 10 64-bi operating system. The exact solution obtained by solving the mathematical model is by the CPLEX12.9 solver.

5.1. Experimental Parameters

By reading the literature related to location-routing problem and reviewing the published vehicle data of relevant companies, the following parameters are given. Otherwise, some parameters (e.g., coordinate of demand nodes) are randomly generated within a reasonable range.

-

speed of vehicles: $v_c$ = 1 km/min ([35]);

-

cost of transporation per minute: $c_1$ = 0.5 CNY/km ([18]);

-

renting cost per time: $c_2$ = 200 CNY/km ([36]);

-

capacity of small vehicles: $Q_c$ = 1800 kg;

-

capacity of large vehicles: $Q_t$ = 6000 kg;

-

coordinate range of demand nodes and recycling sites: randi([10,100],$\left|U\right|$,2)

-

coordinate range of the recycling centre: randi([110,150],1,2);

-

time window of demand node i: $e_i$=randi(300,1,$\left|N\right|$), $ch{a}_i$ = randi([20,70],1,$\left|N\right|$), and $l_i$ = $e_i$ + $ch{a}_i$;

-

processing time of demand node i: $t_i$= randi(120, 1, $\left|N\right|$);

-

amount of e-waste in demand node i: $q_i$= randi([50,1000], 1, $\left|N\right|$);

-

amount of e-waste sent by customers in m: $w_i$ = randi([2000,3000], 1, $\left|M\right|$);

5.2. Numerical Results

Table 2. Computational results of small-scale instances.

Instances			CPLEX		GA			TSGL
[$\left|\mathit{N}\right|$,$\left|\mathit{M}\right|$]	${\mathit{m}}_{\mathbf{1}}$	${\mathit{b}}_{\mathit{m}}^{\mathit{v}}$	$\mathit{Obj}$	$\mathit{Time}$	$\mathit{Obj}$	$\mathit{Time}$	${\mathit{Gap}}_{\mathbf{1}}$	$\mathit{Obj}$	$\mathit{Time}$	${\mathit{Gap}}_{\mathbf{2}}$
	1	[1,1]	584.0	1.1	584.0	9.3	0.0	584.0	0.2	0.0
	2	[1,1]	259.5	1.1	259.5	9.7	0.0	267.0	0.3	2.9
	1	[2,2]	208.0	1.4	208.0	10.6	0.0	216.0	0.3	3.6
[5,2]	2	[2,2]	208.0	1.4	208.0	10.6	0.0	216.0	0.3	3.6
	1	[1,1]	259.5	1.1	259.5	9.7	0.0	267.0	0.3	2.9
	1	[1,2]	432.5	1.3	432.5	10.7	0.0	584.0	0.3	35.0
	2	[1,2]	259.5	1.3	259.5	10.3	0.0	267.0	0.3	2.9
no time windows, $m_1$ = 1			146.5	1.5	146.5	10.4	0.0	162.5	0.3	10.9
Avg			299.9	1.3	299.9	10.2	0.0	328.1	0.4	8.4
	2	[1,1,1]	1159.5	3.4	1159.5	11.1	0.0	1166.5	0.4	0.6
	3	[1,1,1]	853.0	3.5	853.0	12.3	0.0	934.5	0.4	9.5
	2	[2,2,2]	437.5	5.3	437.5	14.0	0.0	443.5	0.4	1.4
[10,3]	3	[2,2,2]	437.5	7.7	437.5	14.3	0.0	443.5	0.4	1.4
	2	[2,1,3]	451.5	5.3	451.5	14.3	0.0	558.5	0.4	23.8
	3	[2,1,3]	451.5	5.3	451.5	14.3	0.0	558.5	0.4	23.8
no time windows, $m_1$ = 2			314.5	21.2	314.5	13.4	0.0	343.0	0.4	9.1
Avg			586.4	7.4	586.4	13.4	0.0	635.4	0.4	9.9
	2	[2,2,2,2,2]	897.0	278.3	1064.5	17.9	18.7	1107.5	0.5	4.0
	3	[2,2,2,2,2]	378.0	26.1	398.0	19.4	5.3	581.5	0.4	46.1
	2	[3,3,3,3,3]	392.0	25.4	399.5	21.4	1.9	541.0	0.5	35.4
[15,5]	3	[3,3,3,3,3]	375.5	37.7	379.5	23.0	1.0	579.5	0.5	52.7
	2	[2,3,2,3,1]	506.5	38.7	522.0	20.0	3.1	585.5	0.5	12.2
	3	[2,3,2,3,1]	439.0	34.5	465.5	20.3	6.1	572.0	0.5	22.9
no time windows, $m_1$ = 2			756.0	832.4	792.0	17.5	4.8	820.0	0.5	3.5
Avg			498.0	73.5	538.2	20.3	6.0	661.2	0.5	28.9
	2	[2,2,2,2,2]	1678.5	1516.9	1977.0	19.0	17.8	2220.5	0.7	12.3
	3	[2,2,2,2,2]	899.5	4639.3	1107.5	21.0	23.1	1148.5	0.7	3.7
	2	[3,3,3,3,3]	-	-	1024.5	23.3	-	1054.5	0.7	2.9
[20,5]	3	[3,3,3,3,3]	476.0	734.5	507.5	26.5	6.6	724.5	0.6	42.8
	2	[2,3,2,3,2]	930.0	1157.6	1102.5	18.5	40.1	1202.0	0.6	9.0
	3	[2,3,2,3,2]	511.0	354.7	538.0	23.8	5.3	743.0	0.7	38.1
no time windows, $m_1$ = 2			-	-	834.0	37.9	-	850.5	1.5	2.0
Avg			899.0	1680.6	1013.0	24.3	18.6	1134.8	0.8	15.8
	3	[2,2,2,2,2,2,2,2]	-	-	1285.0	24.8	-	1356.5	1.2	5.6
	4	[2,2,2,2,2,2,2,2]	523.5	270.0	621.0	26.1	18.6	724.5	0.6	16.7
	3	[2,2,2,2,2,2,2,2]	524.0	841.7	579.5	30.5	10.6	744.5	1.1	28.4
[20,8]	4	[2,2,2,2,2,2,2,2]	520.0	571.1	547.8	32.7	5.3	744.5	0.6	35.9
	3	[2,2,2,2,2,2,2,2]	569.0	3169.2	602.0	27.5	5.8	776.5	0.6	29.0
	4	[2,2,2,2,2,2,2,2]	522.0	135.8	582.0	26.7	11.5	822.5	0.6	41.3
no time windows, $m_1$ = 2			-	-	543.2	28.9	-	682.0	0.7	25.6
Avg			531.7	997.6	680.1	28.2	10.4	835.9	0.8	26.1

and

Table 3. Computational results of large-scale instances.

Instances			GA		TSGL
[$\left|\mathit{N}\right|$,$\left|\mathit{M}\right|$]	${\mathit{m}}_{\mathbf{1}}$	${\mathit{b}}_{\mathit{m}}^{\mathit{v}}$	$\mathit{Obj}$	$\mathit{Time}$	$\mathit{Obj}$	$\mathit{Time}$	${\mathit{Gap}}_{\mathbf{2}}$
	3	[2,2,2,2,2,2,2,2]	1616.0	34.8	1719.5	1.0	6.4
	4	[2,2,2,2,2,2,2,2]	1146.3	39.8	1193.5	1.1	4.1
	3	[3,3,3,3,3,3,3,3]	683.4	46.5	851.0	1.1	24.5
[25,8]	4	[3,3,3,3,3,3,3,3]	708.0	48.8	847.0	1.1	19.6
	3	[3,2,2,3,2,2,2,3]	891.6	30.8	944.0	0.7	5.9
	4	[3,2,2,3,2,2,2,3]	703.9	32.5	778.0	0.8	10.5
Avg			958.2	38.9	1055.5	1.0	6.1
	4	[2,2,2,2,2,2,2,2,2,2]	1786.2	32.5	1872.0	1.1	4.8
	5	[2,2,2,2,2,2,2,2,2,2]	1244.6	35.5	1462.5	0.9	17.5
	4	[3,3,3,3,3,3,3,3,3,3]	1018.8	42.6	1218.5	0.9	19.6
[35,10]	5	[3,3,3,3,3,3,3,3,3,3]	902.6	45.2	1345.5	0.9	49.1
	4	[2,2,1,2,1,3,1,2,1,2]	2504.2	30.4	2917.5	0.8	16.5
	5	[2,2,1,2,1,3,1,2,1,2]	1709.0	36.5	1986.5	0.8	16.2
Avg			1527.6	37.1	1800.4	0.9	20.6
	5	[2,2,2,2,2,2,2,2,2,2,2,2]	2618.6	58.9	2667.5	1.6	1.9
	6	[2,2,2,2,2,2,2,2,2,2,2,2]	1669.3	66.2	1709.5	1.6	2.4
	5	[3,3,3,3,3,3,3,3,3,3,3,3]	1204.6	82.1	1360.0	1.6	12.9
[45,12]	6	[3,3,3,3,3,3,3,3,3,3,3,3]	1155.4	88.9	1383.0	1.6	19.7
	5	[2,3,4,2,3,2,2,2,2,3,2,3]	1256.5	75.8	1310.5	1.6	4.3
	6	[2,3,4,2,3,2,2,2,2,3,2,3]	1305.5	77.8	1415.0	1.6	8.4
Avg			1535.0	75.0	1640.9	1.6	7.1
	6	[2,2,2,2,2,2,2,2,2,2,2,2,2,2]	2919.0	71.4	3013.0	1.8	3.2
	7	[2,2,2,2,2,2,2,2,2,2,2,2,2,2]	2118.4	77.2	2554.0	1.9	20.6
	6	[3,3,3,3,3,3,3,3,3,3,3,3,3,3]	1338.3	98.0	1474.0	1.8	10.1
[50,14]	7	[3,3,3,3,3,3,3,3,3,3,3,3,3,3]	1188.4	103.5	1343.5	1.8	13.1
	6	[2,3,4,3,2,3,3,3,3,3,2,3,2,3]	1377.8	96.2	1576.5	1.8	14.4
	7	[2,3,4,3,2,3,3,3,3,3,2,3,2,3]	1318.1	95.9	1369.0	1.8	3.9
Avg			1710.0	90.4	1888.3	1.8	10.9
	7	[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]	3227.2	56.2	3324.0	1.3	3.0
	8	[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]	2495.9	60.6	2514.5	1.3	0.7
	7	[3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3]	1708.6	78.2	1840.5	1.4	7.7
[55,16]	8	[3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3]	1672.2	82.2	1815.0	1.5	8.5
	7	[2,3,2,2,3,3,1,2,1,2,3,2,2,3,3,2]	1934.1	64.4	2054.0	1.5	6.2
	8	[2,3,2,2,3,3,1,2,1,2,3,2,2,3,3,2]	1716.4	69.5	1813.5	1.2	5.7
Avg			2125.7	68.5	2226.9	1.4	5.3

show the computational results of small-size and large-size instances. The first three columns are parameters of [$\left|N\right|$, $\left|M\right|$], $m_1$, and $b_m^v$. Columns 4 and 5 are results related to CPLEX. Columns 6, 7, and 8 are results related to GA. Additionally, the last three column are results related to TSGL. Among them, Obj denotes the objective function value of each instance, $Ga{p}_1=\frac{GA-CPLEX}{CPLEX}\ast 100\%$ and $Ga{p}_2=\frac{TSGL-GA}{GA}\ast 100\%$, where $Avg$ denotes the mean value of each group that consists of seven instances.

By Table 2, it can be concluded that CPLEX can obtain optimal values in most small-scale cases. However, for large-scale instances, CPLEX cannot output even feasible solutions within the limited time (i.e., 2 h). When scale increases, the run time of CPLEX increases rapidly from 1.4 s to 7200 s. The run time of GA also increases with the increase in scale, but the feasible solution can be obtained in a short time while the time of the heuristic algorithm is very short, and the feasible solution can be obtained in 2 s. In terms of the quality of the solution, optimal values can be obtained, such as in the first and second groups of examples, and $Ga{p}_1$ is 0. With the increase in size, the gap between the feasible solution and the optimal solution gradually increases. It can be seen that the average gap between GA and the exact solution obtained by CPLEX for each group of instances is between 0% and 18.6% and that the average gap between TSGL and GA is between 8.4% and 28.9%. The average gap between GA and CPLEX is about 7.0% in total, and the average gap between TSGL and GA algorithm is about 17.8% in total.

Table 2 shows the experimental results of large-scale instances. Since the CPLEX solver cannot obtain the optimal value within 7200 s for the large-scale instances, the results of GA algorithm and heuristic algorithm are only compared and analyzed. It can be seen from the run time that GA increases gradually with the increase in the scale. The average run time of each group is between 37.1 s and 90.4 s while the run time of the heuristic algorithm is very stable, and the average time is between 0.9 s and 1.8 s. It can be seen that the solving time of the heuristic algorithm is much shorter than that of the genetic algorithm. In terms of the objective value, the average gap of large-scale instances is between 5.3% and 20.6%.

6. Conclusions

This paper presents an optimization model of an e-waste recycling network when considering renting social idle vehicles. In order to meet all of the demands of demand nodes within their expected time windows, with a limited number of own vehicles, idle social vehicles are allowed to be rented in the sharing economy environment to reduce the total operating cost of the recycling logistics network. Meanwhile, both the selection of recycling sites and the delivery routes of owned vehicles need to be determined. The genetic and a two-stage greedy algorithm are proposed to solve the problem, and numerical results demonstrate the effectiveness of two algorithms by small-scale and large-scale instances.

In a recycling network, the recycling sites and owned vehicles equipped need large amounts of capital investment. As a result, it is essential to decide the locations of recycling sites on the basis of recycling demands. Considering renting social idle vehicles when recycling demands surge, leading to a shortage of owned vehicle, is wise and economic because it only costs a small rental fee compared with equipping more vehicles for service.

This study is limited in that the processing time of recycling in demand nodes and the number of demand nodes are considered deterministic. To address this limitation, developing a random and undetermined model of the e-waste recycling location routing problem is a worthwhile topic for future research. Otherwise, another direction for future research is considering multi-objective location routing problems. Last but not the least, from a solution approach perspective, more efficient heuristic or meta-heuristic algorithms should be developed for the considered problem.