Using Simulated Annealing to Solve the Multi-Depot Waste Collection Vehicle Routing Problem with Time Window and Self-Delivery Option

Abstract

This research introduces the Multi-Depot Waste Collection Vehicle Routing Problem with Time Windows and Self-Delivery Option (MDWCVRPTW-SDO). The problem comes from the waste bank operation implemented in Yogyakarta City, Indonesia. A set of vehicles is dispatched from the waste banks to pick up waste from residents’ locations within the time windows specified by the residents. Residents may be compensated for delivering their waste to a waste bank by themselves. The objective of MDWCVRPTW-SDO is minimizing the sum of investment costs, routing costs, and total compensation paid to the residents. We model this problem as a mixed integer linear programming model and propose Simulated Annealing (SA) as an effective solution approach. Extensive computational experiments confirm that SA is effective to solve MDWCVRPTW-SDO. Moreover, the number of waste banks, compensation paid to residents, and the distribution of residents of each type are crucial for the success of the implementation.

1. Introduction

Waste has become a harmful yet unavoidable part of human life. Poor practices such as illegal disposal, waste burning in open spaces, and low waste collection rates still occur in many cities of developing countries [1]. These improper waste disposal practices may lead to environmental, health, and aesthetic harms [1,2,3,4]. In developing countries, the increasing number of wastes produced and ineffective waste management have become common problems encountered by the local authorities and governments [2,3,5]. Thus, developing an appropriate waste management is a high priority. Effective and sustainable waste management could protect the health of the population, encourage environmental quality, develop sustainability, and support economic productivity [5].

Many developing cities in Asia are overwhelmed by increasing waste due to their growing population [2,6,7], as in the case of Yogyakarta City, Indonesia, where population growth positively correlates to the volume of waste produced there [1]. According to the Central Bureau of Statistics of Yogyakarta Special Region, the total population of Yogyakarta City is growing by 1.2% every year and it hit 435,936 in 2020. Moreover, among all cities that send their wastes to the same waste processing center, Yogyakarta City is recorded as the largest waste producer as it contributes 44% of total waste [8]. Considering the aforementioned fact, the local authorities of Yogyakarta City are in need of developing an innovative waste management program to cope with the growth of waste volume.

Waste collection commonly involves a set of vehicles serving a set of collection points to pick up solid/recyclable waste and deliver the waste to a disposal facility; e.g. a recycling plant, an energy recovery facility, or a landfill [9]. Thus, this problem is considered as a reverse logistic problem where the vehicle has to visit many locations for pick-ups and finally deliver the collected goods to one delivery point [9,10,11,12]. Due to the activities involved in waste collection, the resulting problem belongs to a group of well-known combinatorial problems, i.e., the vehicle routing problem (VRP). With the resultant complexity, efficiently dispatching vehicles becomes a critical factor in waste management among other things like environmental, economic, logistical, technical, and political factors [13].

Considering the fact that a significant impact may be incurred due to improper waste management, local authorities have put forth efforts to develop innovative solutions for the waste collection process [2]. Here, in this research, we consider the implementation of a particular waste collection facility called waste bank, which is an initiation of the local authority of Yogyakarta City to deal with recyclable waste. A waste bank aims to reduce the amount of recyclable waste from households by collecting and sorting inorganic waste that still can be reused and recycled. The idea of this facility is that a resident will reach a waste bank to deliver his/her recyclable waste. However, waste banks in Yogyakarta City are currently underutilized [3,14]. Several alternatives for increasing the utilization of waste banks have been proposed, such as providing incentives [14] and an additional option, like a pick-up service [15].

This research addresses an optimization problem taking the form of a waste collection problem arising from the implementation of waste banks in Yogyakarta City, Indonesia. The setting of this problem involves a set of waste banks and residents. In particular, due to the existence of waste banks and the pick-up service, a resident may (1) request a home pick-up at his/her location, (2) deliver his/her waste to a waste bank, and (3) be flexible depending on the assignment of the waste collection centralized system. A fleet of vehicles is available at each waste bank to pick up recyclable waste from residents who request pick-up service or are selected by the system to be served by said service. Moreover, a customer who delivers his/her waste to a waste bank receives an amount of compensation in exchange for the effort he/she put forth. The centralized system aims to serve these residents at a minimized cost. Considering the described characteristics, the problem is called the Multi-Depot Waste Collection Vehicle Routing Problem with Time Windows and Self-Delivery Option (MDWCVRPTW-SDO). To the best of our knowledge, there is no previous work in the waste collection literature that addresses the same features as we consider herein. Further reviews are provided in the Section 2. Finally, the contributions of this work are summarized as follows.

• Propose a new variant of waste collection routing problem, called the Multi-Depot Waste Collection Vehicle Routing Problem with Time Windows and Self-Delivery Option.
• Develop a mixed integer linear programming model for the formulation of the problem.
• Propose a simulated algorithm metaheuristic to solve instances of various sizes of the problem.
• Provide sensitivity analysis that can offer managerial insights based on a real-world situation obtained from Yogyakarta City, Indonesia.

The remainder of the paper is organized as follows. Section 2 reviews relevant literature. Section 3 describes the problem and the mathematical model for the problem. Section 4 discusses methodology for this problem. Section 5 presents experimental results. Section 6 provides conclusions and points out potential directions for future studies.

2. Literature Review

We present a non-exhaustive literature review on the application of VRPs in residential waste management and various solution approaches developed to tackle the resulting problem. Tung and Pinnoi [16] pioneer the research on tackling a real-world street solid waste collection system in the inner city by VRP. A fleet of specialized trucks departs from the depot and visits a set of locations called gather sites to pick up waste collected from households or industrial units. If a truck is fully loaded, then the truck will visit a landfill. Another trip is performed if the total operational time of the truck has not reached the maximum working time of the given planning period. Thus, a truck possibly visits the landfill more than once before returning to the depot.

Another interesting characteristic of the problem is that each gather site may be visited more than once with a minimum inter-arrival time applied to consecutive visits due to the time required to fill up the gather site. Consequently, each gather site may have multiple time windows. Kim et al. [17] formalize the application of VRP to waste management by naming the problem waste collection vehicle routing problem with time windows and investigate a similar problem in [16] with two notable differences: considering multiple landfills to reduce the operational cost and explicitly handling the break time of drivers. Since then, waste collection routing problems have gained momentum and many applications have been developed [18].

An ongoing development of the research in this area is integrating unique problem characteristics either to achieve a more effective solution, in terms of operational costs, or to address real-world cases. Reed et al. [19] and Abdulkader et al. [20] consider a fleet of multi-compartment vehicles, such as vehicles equipped with multiple compartments containing different types of waste, with the aim of improving the quantity or quality of the recyclable material produced. Exposito-Marquez et al. [21] tackle the recyclable waste collection system by considering the fill rate of each bin spread over the considered area. The purpose is to maximize the collected recyclable waste over the given planning period. Wei et al. [22] propose an approach called Midway Disposal Pattern by relaxing the assumption in [16,17]; i.e., a truck will go to the landfill only if it is fully loaded. In other words, the proposed approach allows trucks to dump their current loads even though they are partially loaded. This approach is proposed to reduce the carbon emission produced by utilized trucks as the amount of carbon emission depends on the total loads carried. Due to a stricter regulation forcing new landfills to be located further from the residential areas, Ghiani et al. [23] propose a two-echelon waste collection system in which smaller vehicles operate to collect waste from the collection points where waste is generated and transfer the waste to the waste transfer stations before vehicles of a larger capacity pick up the waste at transfer stations. Similarly, Yu et al. [24] study a two-echelon waste collection system with a distinctive feature, i.e., considering different types of costs that lead to a multi-objective optimization problem.

The scope of waste collection routing problems commonly deals with the operational level, i.e., route planning for a relatively short planning period such as days or weeks. However, integrating strategic-level decisions into waste collection routing problems may arguably result in more efficient operations for waste management in the long term. Hemmelmayr et al. [25] propose a model for the integrated problem, simultaneously addressing the strategic-level and operational-level decisions. The strategic-level decision involves the number and configuration of bins at collection points, which leads to the determination of investment costs. The analysis emphasizes the trade-off between the investment costs resulting from the bins and the operational costs obtained from the solutions collected from solving the waste collection routing problem. Shang et al. [26] deal with another integrated problem: deciding the number and the locations of waste collection facilities with waste collection route planning. They are the first to explicitly deal with the queueing time occurring at the waste collection facilities. Consequently, the resulting problem leads to a more complex trade-off among investment costs, operational costs, and total penalty costs resulting from the queueing time of vehicles at waste collection facilities. Tirkolaee et al. [27] develop a novel mixed-integer linear programming (MILP) model for the sustainable periodic capacitated arc routing problem (PCARP) in municipal solid waste management. The model aims to minimize total cost, environmental emissions, and workload deviation while maximizing citizen satisfaction.

The development of information and technology has unlocked various innovative improvements made for waste management. The first is the improvement that focuses on the vehicles. Erdem [28] and Erdinç et al. [29] investigate route planning for waste collection with a fleet of electric vehicles, aiming to support a sustainable waste collection mechanism. The second improvement is the integration of a real-time technology, like the Internet of Things, to detect the condition of bins at collection sites [30,31,32,33]. The main purpose is to minimize the operational cost while maximizing the collected waste from the visited collection points [34,35,36,37]. The growing trend of machine learning has influenced research in this area. Vu et al. [38] integrate a machine learning technique called Artificial Neural Network to predict the demand in collection points, which provides better input for the route planning of waste collection.

We briefly discuss the connection of various route plans for waste collection to the well-established variants in the VRP. The landfills described in [16,17,22] are locations visited by vehicles to dump collected waste, and the vehicles are allowed to visit other collection points as long as this respects the other operational constraints. In other words, the landfills act as intermediate stops.

The utilization of electric vehicles for waste collection such as by Erdem [28] and Erdinç et al. [29] can also be seen as another variant of problems that utilize intermediate stops; e.g., electric vehicles may need to stop for a certain period of time at recharging stations to increase their battery states. Schiffer et al. [39] provide a unifying literature review of a class of VRP that considers intermediate stops (VRPIS). The multi-compartment vehicles considered in [19,20] are commonly used in other logistics activities for specific products, such as temperature-sensitive groceries and petrol, called the Multi-Compartment Vehicle Routing Problem (MCVRP) [40].

Ghiani et al. [23] and Yu et al. [24] both investigate the waste collection system under a two-echelon structure. This structure is a well-known distribution system invented as a result of the policy for limiting the movement of large vehicles in several cities. Sluijk et al. [41] propose the most recent review on various two-echelon vehicle routing problems (2E-VRPs) investigated in the body of literature. Hemmelmayr et al. [25] and Shang et al. [26] consider two integrated problems in which both strategic and operational-level decisions are involved. This integrated problem has been addressed and named the Location-Routing Problem (LRP) [42].

In this research, we consider route planning for waste collection, which is derived from a different variant of VRP previously mentioned. MDWCVRPTW-SDO is a generalization of the multi-depot vehicle routing problem with time windows (MDVRPTW) in which several depots and a set of vehicles are available to serve customers within predetermined time windows. So far, to the authors’ knowledge, this problem inspired by a real-world case study in Indonesia has never been investigated and hence contributes to the body of literature related to the adoption of a VRP variant in handling route planning for waste collection. We summarize the relevant literature in

Table 1. Summarized relevant literature on waste collection vehicle routing problem.

Publication	Variant of VRP	Objective	Solution Method	Case Study Location
Tung and Pinnoi [16]	Vehicle routing and scheduling problem (VRSP)	Minimize total operating cost	Heuristic (construction phase and improvement phase)	N/A
Kim et al. [17]	Vehicle routing problem with time windows (VRPTW)	Minimize number of vehicles and total travel time	Capacitated clustering-based heuristic	Waste Management, Inc. in North America
Reed et al. [19]	MCVRP	Minimize the cost of multi-compartment waste collection	Ant colony system (ACS)	N/A
Abdulkader et al. [20]	MCVRP	Minimize total travel distance	Hybridized local search and ant colony optimization (ACO)	N/A
Exposito-Marquez et al. [21]	Eco-efficient vehicle routing problem (Ee-VRP)	Maximize fill level of the collected containers	Greedy randomized adaptive search procedure (GRASP)	Island of La Palma (Canary Islands, Spain)
Wei et al. [22]	Waste collection problem with midway disposal pattern collection problem (WCP-MDP)	Minimize total carbon emission costs	Artificial bee colony (ABC)	N/A
Ghiani et al. [23]	Two echelon waste collection	Minimize number of collection vehicles used	Two-phase heuristic	N/A
Yu et al. [24]	Two-echelon multi-objective location routing problem (2E-MOLRP)	Minimize total cost including vehicle-related costs, facility-related costs, and routing-related costs	Improved non-dominated sorting genetic algorithm with directed local search (INSGA-dLS)	N/A
Hemmelmayr et al. [25]	Waste bin allocation and routing problem (WBARP)	Minimize purchase, removal, and transfer costs.	Variable neighborhood search (VNS)	N/A
Shang et al. [26]	Capacitated location routing problem with queuing time (CLRPQT)	Minimize total cost including transportation cost, operating cost of facilities, collection cost, and penalty cost of waiting	Simulated annealing-based hyper-heuristic	Simulated data for Shanghai, China
Erdem [28]	Electric waste collection problem (EWCP)	Minimize total travel cost	Adaptive variable neighborhood search (AVNS)	N/A
Erdinç et al. [29]	Waste collection vehicle routing problem (WCVRP)	Minimize total energy consumption of all electric garbage trucks	MILP	Bakirkoy Municipality, Istanbul, Turkey
Roy et al. [34]	IoT-based vehicle routing problem	Minimize the sum of bin allocation cost, routing cost, driver wages, and penalty cost	Hybridized VNS and ACO	South Korea
Ramos et al. [35]	Smart waste collection routing problem (SWCRP)	Minimize transportation cost and maximize total profit	MILP	Valorsul company in Western Waste Treatment Centre.
Hannan et al. [36]	Capacitated Vehicle Routing Problem (CVRP)	Minimize distance or total cost	Particle swarm optimization (PSO)	N/A
Vu et al. [38]	CVRP	Minimize total travel distance and emissions	Artificial neural network (ANN)	N/A
Campos and Arroyo [43]	Waste collection vehicle routing problem with time windows (WCVRPTW)	Minimize total travel cost	Hybridized iterated local search (ILS) and variable neighborhood descent (VND)	N/A
Wu et al. [44]	Priority considered green vehicle routing problem (PCGVRP)	Minimize total distance and total emissions costs	Local search hybrid algorithm (LSHA)	N/A
Mohammadi et al. [32]	Dynamic vehicle routing problem (DVRP)	Minimize overall transportation cost and the associated penalty for CO2 emissions	Hybridized genetic algorithm (GA) and PSO	N/A
Rahmanifar et al. [33]	Green CVRP	Minimize transportation cost, CO2 emissions, and the cost of transferring waste to recycling centers	Hybridized SA and hybridized social engineering optimizer (SEO) with nine heuristics	N/A
Bouleft and Elhilali Alaoui [30]	Dynamic multi-compartment vehicle routing problem (DM-CVRP)	Minimize total cost including transportation cost and penalty cost	Hybridized GA	N/A
Tirkolaee et al. [27]	Periodic capacitated arc routing problem (PCARP)	Minimize total cost, minimize total emissions, maximize citizen satisfaction, and minimize workload deviation	Hybridized multi-objective SA and multi-objective invasive weed optimization algorithm (MOSA-MOIWOA)	N/A
Hashemi-Amiri et al. [31]	Heterogeneous fleet VRP with hard time windows (HVRPHTW)	Maximize the probabilistic profit, and minimize total travel time and transportation costs	Goal programming (GP) and four multi-objective metaheuristics	N/A

. It can be seen that case studies for the waste collection vehicle routing problem are rare.

3. Problem Description and Mathematical Model

The aim of this research is to address a new variant of a waste collection vehicle routing problem arising from recyclable household waste collection in Yogyakarta City, Indonesia, called the Multi-Depot Waste Collection Vehicle Routing Problem with Time Window and Self-Delivery Option. A set of waste banks serves as a collection point for all recyclable household waste. Each waste bank provides two service options for each resident: picking up waste at a resident’s location or providing a self-delivery option for residents to willingly drop off their waste. Consequently, residents are categorized into the following three types.

(1)

Type 1 resident: Home pick-up resident. The resident requires his/her waste to be picked up by a waste bank at his/her home.

(2)

Type 2 resident: Self-delivery resident. The resident willingly drops off the waste him/herself to a waste bank assigned by the system.

(3)

Type 3 resident: Flexible resident. The resident is flexible in terms of waste collection methods. This resident can hence be assigned to be a home pick-up resident or a self-delivery resident, determined by the waste collection system.

The assumptions for this problem are as follows:

(1)

The total waste of each resident is known and deterministic.

(2)

Each resident must be served based on their category.

(3)

The waste amount of each resident is determined by taking an average of the total household waste volume in historical data.

(4)

Each vehicle has a limited capacity.

(5)

The number and locations of the waste banks are predetermined.

(6)

The average speed of all vehicles is the same.

(7)

Each waste bank has the same operational hour/time window.

(8)

Each waste bank has the same number of available vehicles.

(9)

Each vehicle returns to the waste bank from which the vehicle starts.

Figure 1 illustrates a solution for MDWCVRPTW-SDO with four waste banks and 15 residents consisting of 5 home pick-up residents, 6 self-delivery residents, and 4 flexible residents. Among the four existing waste banks, only three waste banks are utilized: WB1 and WB4 both serve home pick-up and self-delivery residents, while WB2 only serves self-delivery resident R6 without any home pick-up resident being served. Each resident who is served at his/her location is visited with respect to the time windows defined by the resident. Each resident performing the self-delivery option visits a waste bank that is reachable by the resident. From the illustration, some flexible customers, like R3 and R13, are served at their locations while the remaining flexible customers, R7 and R9, are assigned as self-delivery residents.

The parameters and decision variables used in the MILP are as follows.

Parameters:

$i, j$	Index of resident or waste banks.
$k$	Index of vehicle.
$f$	The fixed cost of the vehicle.
$v$	The variable cost of the vehicle per unit distance.
$K$	Set of vehicles.
$n$	Number of residents.
$m$	Number of vehicles for each waste bank.
$\theta$	Maximal covering range for self-delivery resident.
$Q$	The loading capacity of vehicles.
$N_{SS}$	Set of home pick-up residents (Type 1 residents).
$N_{PS}$	Set of home self-delivery residents (Type 2 residents).
$N_{SPS}$	Set of home flexible residents (Type 3 residents).
$N_C$	$\mathrm{Set} \mathrm{of} \mathrm{residents} (N_C=N_{SS}\cup N_{PS}\cup N_{PS}$).
$N_D$	Set of waste banks.
$N$	$\mathrm{Node} \mathrm{set} (N=N_D\cup N_C)$.
$q_i$	Waste amount of the resident $i$.
$s_i$	Service time of the resident $i$.
$e_i$	The earliest arrival time of the type 1 or type 3 resident $i$.
$l_i$	The latest arrival time of the type 1 or type 3 resident $i$.
$W_j$	The maximum capacity of wastes that can be collected for waste bank $j$.
$r_{ij}$	Traveling cost from node $i$ to $j$.
$t_{ij}$	Traveling time from node $i$ to $j$.
$p_{ij}$	The total compensation cost paid for residents $i$ who send the his/her waste to waste bank $j$ by self-delivery (either type 2 resident or type 3 resident assigned to as self-delivery resident).
$M$	A sufficiently large number.

Decision Variables:

$X_{ijk}$	Binary variable. 1 if vehicle $k$ travels from node $i$ to j and 0 otherwise.
$Y_{ik}$	Binary variable. 1 if waste bank $i$$\mathrm{is} \mathrm{and} \mathrm{vehicle} k$ is used and 0 otherwise.
$H_i$	Binary variable. 1 if resident $i$ is served with pick-up service and 0 otherwise.
$D_i$	Binary variable. 1 if resident $i$ is served with self-delivery and 0 otherwise.
$B_{ij}$	Binary variable. 1 if resident $i$ sends the waste to waste bank j by self-delivery and 0 otherwise.
$S_{ik}$	The time vehicle $k$ starts the service at resident.
$A_{jk}$	The time vehicle $k$ departs from waste bank j.
$R_{jk}$	The time vehicle $k$ returns to waste bank j.
$u_i$	Auxiliary variables used to avoid sub-tours.

Objective Function:

$$\min Z=f\sum _{i\in N_D}\sum _{k\in K}{Y}_{ik}+v\sum _{i\in N,i\ne j}\sum _{j\in N,j\ne i}\sum _{k\in K}{x}_{ijk}{r}_{ij}+\sum _{i\in N_C}\sum _{j\in N_D}{p}_{ij}{B}_{ij}$$

(1)

Constraints:

$$\sum _{\begin{array}{c}i\in N\\ i \ne j\end{array}}{x}_{ijk}-\sum _{\begin{array}{c}i\in N\\ j\ne i\end{array}}{x}_{jik}=0,\forall j\in N,\forall k\in K$$

(2)

$$\sum _{kϵK}\sum _{jϵN}{x}_{ijk}=H_i,\forall i\in N_{SS}\cup N_{PS}\cup N_{SPS}$$

(3)

$$\sum _{iϵN_D}\sum _{jϵN_D}{x}_{ijk}=0,\forall k\in K$$

(4)

$$\sum _{iϵN}\sum _{\begin{array}{c}jϵN_C\\ i\ne j\end{array}}{q_{j}x}_{ijk}\le Q,\forall k\in K$$

(5)

$$S_{ik}+s_i+t_{ij}-S_{jk}\le M\left(1-x_{ijk}\right),\forall i\in N_D\cup N_{PS}\cup N_{SPS},\forall j\in N_{PS}\cup N_{SPS},\forall k\in K$$

(6)

$$S_{ik}+s_i+t_{ij}\le l_j+M\left(1-x_{ijk}\right),\forall i\in N_D\cup N_{PS}\cup N_{SPS},\forall j\in N_D,\forall k\in K$$

(7)

$$S_{ik}\le M\sum _{jϵN}{x}_{jik},\forall i\in N_C,\forall k\in K$$

(8)

$$e_i{+(H}_i-1)M\le \sum _{kϵK}{S}_{ik}\le l_i+(1-H_i)M,\forall i\in N_{PS}\cup N_{SPS}$$

(9)

$$A_{jk}+t_{ji}-S_{ik}\le M\left(1-x_{jik}\right), \forall i\in N_{PS}\cup N_{SPS},\forall j\in N_D, \forall k\in K$$

(10)

$$S_{ik}+s_i-t_{ij}-R_{jk}\le M\left(1-x_{ijk}\right), \forall i\in N_{PS}\cup N_{SPS}, \forall j\in N_D, \forall k\in K$$

(11)

$$R_{jk}-A_{jk}\le T, \forall j\in N_D, \forall k\in K$$

(12)

$$H_i+D_i=1,\forall i\in N_C$$

(13)

$$H_i=1,\forall i\in N_{PS}$$

(14)

$$D_i=1,\forall i\in N_{SS}$$

(15)

$$\sum _{jϵN_D}{B}_{ij}=D_i,\forall i\in N_C$$

(16)

$$\sum _{iϵN_C}{B}_{ij}{q}_i+\sum _{iϵN_C}\sum _{\begin{array}{c}kϵK\\ j\ne i\end{array}}{x}_{ijk}{q}_i\le W_j,\forall j\in N_D$$

(17)

$$\sum _{jϵN_D}{Y}_{jk}\le 1,\forall k\in K$$

(18)

$$Y_{jk}\ge \sum _{iϵN_C}{x}_{jik},\forall j\in N_D,\forall k\in K$$

(19)

$$\sum _{iϵN_C}\sum _{jϵN_D}{x}_{ijk}=\sum _{jϵN_D}{Y}_{jk},\forall k\in K$$

(20)

$$B_{ij}{r}_{ij}\le \theta D_i,\forall j\in N_D,\forall i\in N_C$$

(21)

$$\sum _{k\in K}{Y}_{jk}\le m,\forall j\in N_D$$

(22)

$$u_i-u_j+n x_{ijk} \le n-1,\forall i\in N,\forall j\in N_C,\forall k\in K$$

(23)

The objective function (1) of MDWCVRPTW-SDO is to minimize the fixed cost of the vehicles used, the total cost of routing, and compensation paid to self-delivery residents. Constraint (2) guarantees the flow conservation. Constraint (3) ensures a home pickup operation is conducted at a resident’s location if the resident is served as a home delivery resident. Constraint (4) prohibits a vehicle to travel between waste banks. Constraint (5) guarantees that the total amount of waste carried by each vehicle does not exceed the vehicle capacity. Constraints (6)–(9) relate to the time window in this model. In order to track the arrival time for both residents and waste banks, Constraints (6)–(7) are used. Constraint (9) ensures that if a resident is served at his/her home, then s/he must be visited within predefined time windows. The vehicle start time and end time will be determined by Constraints (10) and (11). Constraint (12) guarantees the vehicle traveling time does not exceed the maximum routing time. Constraints (13)–(15) ensure that each resident is served by either home pick-up or drop-off. Constraint (16) ensures that each self-delivery resident will drop-off the waste to a waste bank. Constraint (17) guarantees that total waste collected at each waste bank (from home pick-up and drop-off residents) does not exceed the waste bank capacity. Constraint (18) ensures that one vehicle can only be assigned to one waste bank while Constraint (19) guarantees that a vehicle can depart from a waste bank if the vehicle is assigned to the waste bank. Constraint (20) ensures that there should be a route generated by a vehicle if the vehicle is utilized. Constraint (21) guarantees that only a self-service resident within the covering range can be served by a waste bank for a drop-off service. Constraint (22) guarantees that each waste bank can only dispatch a limited number of vehicles. Finally, Constraint (23) is the well-known Miller–Tucker–Zemlin sub-tour elimination constraints.

4. Methodology

Due to the complexity of MDWCVRPTW-SDO, heuristics become promising alternatives for solving problems with real-life size. A simulated annealing (SA) algorithm is thus developed in this paper. SA has been widely used and has proven its excellent performances in various VRPs such as Capacitated Vehicle Routing Problem [43,45], two-echelon joint delivery location routing problem [46], disaster relief on destructive transportation networks [47], capacitated location-multi allocation-routing problem [48], vehicle routing problem with pick-up and delivery [49], green vehicle routing problem [44], hybrid vehicle routing problem [50], share-a-ride problems [51,52], and a multi-depot two-echelon vehicle routing problem with delivery options [53].

4.1. Solution Representation

The solution representation consists of two parts. The first part ${\sigma }_1=\left\{{\sigma }_1\left(1\right),\dots ,{\sigma }_1 \left(\left|{\sigma }_1\right|\right)\right\}$ is the permutation of type 1 residents and type 3 residents, waste banks, and dummy zeros. In other words, the value of $\left|{\sigma }_1\right|$ is $\left|N_{SS}\right|+\left|N_{SPS}\right|+\left|N_D\right|+\left|N_0\right|$. The first element of ${\sigma }_1$, i.e., ${\sigma }_1\left(1\right)$, is a waste bank. The second part of solution representation ${\sigma }_2=\left\{1,2,\dots ,\left|N_C\right|\right\}$ is used to determine the selected service for each associated resident; i.e., the resident is either served by the vehicle or needs to visit a waste bank to drop off the waste. Let ${\mu }_i^W$ be the number of accessible waste banks by resident $i, \forall i\in N_{PS}\cup N_{SPS}$. If resident $i\in N_{SS}$, then the value of ${\sigma }_2\left(i\right)$ is permanently 1. If resident $i\in N_{PS}$, then the value of ${\sigma }_2\left(i\right)$ ranges from 1 to ${\mu }_i^W$. Lastly, if resident $i\in N_{SPS}$, then the value of ${\sigma }_2\left(i\right)$ ranges from 1 to ${\mu }_i^W+1$, i.e., 1 for being a home pick-up resident and the remaining values for being a self-delivery resident.

Figure 2 and Figure 3 consecutively illustrate ${\sigma }_1$ and ${\sigma }_2$. There are 15 residents denoted by 1 to 15 and four waste banks denoted by 16 to 19. There are four type 3 residents, i.e., 3, 7, 9, and 13. Figure 2 shows the permutation of type 1 residents, type 3 residents, waste banks (shaded entries), and dummy zeros. Based on Figure 3, the values of ${\sigma }_2\left(3\right)$ and ${\sigma }_2\left(13\right)$ are both 1, stating that both are served as type 1 residents, while the values of ${\sigma }_2\left(7\right)$ and ${\sigma }_2\left(9\right)$ are greater than 1 as residents 7 and 9 are assigned as self-delivery residents (shaded entries). The visual illustration of this solution example is shown in Figure 1. It can be seen that resident 7 has two accessible waste banks. If ${\sigma }_2\left(7\right)=1$, resident 7 will be served by a vehicle. If ${\sigma }_2\left(7\right)=2$, resident 7 will go to waste bank 1 (WB1) to drop off the waste. If ${\sigma }_2\left(7\right)=3,$ resident 7 will go to waste bank 2 (WB2) to drop off the waste.

4.2. Evaluation of the Objective Value

We need both ${\sigma }_1$ and ${\sigma }_2$ to calculate the objective value. The procedure starts with ${\sigma }_1$. The first node in ${\sigma }_1$ is a waste bank that becomes the origin location of the currently evaluated vehicle’s route. The next nodes, type 1 residents or type 3 residents, who are served by the home pick-up operation are then added to the current route one by one. The currently evaluated route is terminated when the next node in ${\sigma }_1$ is a dummy zero or a waste bank. Whenever the currently evaluated route is terminated, a new route is initiated. The routine is performed until it reaches the last node of ${\sigma }_1$. If the termination occurs because of a waste bank, then the waste bank becomes the origin of the new route; otherwise, the new route has the same waste bank as the terminated route.

If there is any violation in the time window or load carried by a vehicle when adding a resident node to the currently evaluated route, the route is also terminated by going back to its associated waste bank, and a new route originating from the same waste bank is created, and this resident becomes the first resident served. Vehicles must arrive to residents who are served at their locations within the specified time windows. A vehicle must wait until the earliest time to serve a resident if it arrives earlier. By following this method, it can be verified that this solution representation always gives a solution without violating time windows, the time limit of tours, and the capacity of vehicles. From ${\sigma }_2$, we obtain the total compensations paid to type 2 residents and type 3 residents who are assigned as self-delivery residents. Finally, there are two remaining constraints that are not guaranteed by the abovementioned solution representation: the number of utilized vehicles and the total load assigned to each waste bank. Therefore, the original objective value obtained from the aforementioned procedure $f\left(\sigma \right)$ is modified into $\tilde{f}\left(\sigma \right)$ by utilizing equation (23) to take into account such violations. In Equation (24), $vi{o}_{veh}$ and $vi{o}_{cap}$ consecutively represent the number of extra vehicles and the total extra load assigned to all waste banks.

$$\tilde{f}\left(\sigma \right)=f\left(\sigma \right)+\rho \times (vi{o}_{veh}+vi{o}_{cap})$$

(24)

4.3. Initial Solution

The procedure for generating an initial solution is described below.

• Step 1: For each type 2 resident who can be served by only one waste bank, assign the resident to the associated waste bank.
• Step 2: For each remaining type 2 resident, assign the resident to the nearest reachable waste bank that still has enough capacity and update the remaining capacity of the waste bank. If there are still any remaining type 2 residents, then assign the resident to the nearest waste bank with the highest remaining available capacity. The waste bank is not necessarily reachable and the solution produced is infeasible. However, note that we allow the infeasible solution by utilizing the penalty mechanism introduced in Section 4.2.
• Step 3: For each type 3 resident, choose the nearest available waste bank with enough remaining capacity that can be visited by the resident. If no waste bank can handle the demand of the resident, then the resident will remain unassigned and will be served as a home pick-up resident in Step 4.
• Step 4: For each waste bank $w\in N_W$
  • Step 4.1: Find the resident who can be served in the earliest time and is feasible with respect to the vehicle’s capacity, waste bank’s capacity, and time windows; serve this resident using the currently evaluated vehicle and update the related information of the vehicle. Repeat Step 4.1 until all unserved residents are evaluated.
  • Step 4.2: If all unserved residents are evaluated, then the current vehicle returns to waste bank $w$.
  • Step 4.3: If there are no remaining type 1 and type 3 residents, go to Step 5.
  • Step 4.4: If there is an unused vehicle existing in waste bank $w$, then a new vehicle will be assigned from waste bank $w$; go to Step 4.1.
  • Step 4.5: If all vehicles in waste bank w are utilized, then we move to the next waste bank and employ a new vehicle; go to Step 4.1.
• Step 5: If there are still unused vehicles, then add 0 in the solution representation for each unused vehicle.

4.4. Neighborhood Moves

Four neighborhood moves in the proposed SA are defined as (1) swap, (2) insertion, (3) reversion, and (4) reassign. While the first three operators are widely found in the literature, the last operator is tailored to deal with type 3 residents. The first three operators deal with ${\sigma }_1$, while the last operator specifically deals with ${\sigma }_2$. The swap operator illustrated in Figure 4 operates by randomly selecting two nodes in ${\sigma }_1$ (shaded entries) and exchanging the positions of them. The insertion operator shown in Figure 5 operates by selecting a node randomly from ${\sigma }_1$ and inserting it into a new position (shaded entries). The reversion operator depicted in Figure 6 is performed by selecting a substring of ${\sigma }_1$ and reversing its order (shaded entries). The reassign operator randomly selects a resident from the set of type 2 and type 3 residents and randomly changes the resident’s value in ${\sigma }_2$. For a type 2 resident, the change results in a change in the waste bank to which the resident is assigned to perform the self-delivery option. For a type 3 resident, the change may result in two scenarios. The first scenario is changing the operation assigned to the resident, i.e., from home pick-up to the self-delivery option and vice versa. The second one is similar to the case of type 2 residents and only happens to type 3 residents who are assigned as self-delivery residents.

4.5. SA Parameters

The parameters used in this proposed SA heuristic are $I_{iter}$, $T_0$, $N_{non-improving}$, $\alpha$, and $\rho$. $I_{iter}$ refers to the number of iterations of neighborhood search at a particular temperature. $T_0$ denotes the initial temperature. $N_{non-improving}$ represents the maximum allowable number of temperature reductions without improvement in the objective value. $\alpha$ is a coefficient used to control the speed of the cooling process. Lastly, $\rho$ is the amount of the unit penalty.

4.6. SA Procedure

Figure 7 shows the pseudocode for the proposed SA algorithm. The input of SA is an MDWCVRPTW-SDO instance and the required parameters. The output is the best-found solution ${\sigma }^{*}$. Before SA is executed, we initialize a solution by using a procedure described in Section 4.3 and store the result in ${\sigma }^c$. We then set the probability of each neighbourhood move by using $SetProbability\left(\pi \right)$, where $\pi$ is a vector consisting of the selection probability of each neighborhood move defined in Section 4.4. $SetProbability\left(\pi \right)$ is an equal selection probability for each neighbourhood move. Initially, we set the current temperature $T$ as $T_0$ and ${\sigma }^{*}$ as ${\sigma }^c$.

SA consists of outer and inner loops. The inner loop is the phase in which new solutions are created by means of neighborhood moves and the acceptance mechanism of these newly generated solutions. A new type of solution ${\sigma }^w$ is defined as a temporary solution for the implementation of neighborhood moves. In the beginning of the inner loop, SA copies ${\sigma }^c$ to ${\sigma }^w$. One neighbourhood move is then selected using the function $NeighborhoodMove({\sigma }^w,\pi )$ and is implemented to ${\sigma }^w$, as described in Line 10. The selection is based on the principle of a roulette wheel with the given selection probability $\pi$. Line 12 states that ${\sigma }^w$ is copied to ${\sigma }^c$ if the modified objective value of ${\sigma }^w$ is lower than that of ${\sigma }^c$. Furthermore, Line 14 states the condition for updating ${\sigma }^{*}$. Lines 16 to 18 define the simulated annealing acceptance criterion. The outer loop aims to reduce the temperature T and update the total non-improving iterations ${\mu }_{non-improving}$. Finally, SA terminates when ${\mu }_{non-improving}$ reaches $N_{non-improving}$.

5. Computational Result

The proposed SA metaheuristic was implemented in C programming language in Microsoft Visual Studio C++ 2019 and run on a computer with Intel^® Xeon^® CPU E3-1245 v6 at 3.70 GHz, 16 GB of RAM, and using a 64-bit operating system (Windows 10). In order to verify its performance, SA was tested on well-known instances of MDVRPTW, proposed by Cordeau et al. [54]. In this section, we present the mechanism of generating a set of instances for MDWCVRPTW-SDO, parameter setting, the performance evaluation of our proposed SA, and the result of solving a real-world instance obtained from Yogyakarta City, Indonesia.

5.1. Benchmark Instances

Three sets of MDWCVRPTW-SDO instances are generated for our computational study and one instance generated from real life conditions in Yogyakarta City is generated for sensitivity analysis. The first two sets are mentioned as small and medium instances where each one consists of five instances. The information is directly adopted from the real locations of waste banks in Yogyakarta City, while the locations of residents are randomly generated from the region of Yogyakarta City. The number of waste banks for the small dataset and medium dataset is four and six, respectively. The number of residents for small and medium instances are 15 and 25, respectively. For the last set, we adopt 20 instances of MDVRPTW originally proposed by Cordeau et al. [54]. Each resident will be assigned as either a home delivery, a self-delivery, or a flexible resident randomly. The compensation given to a resident who performs self-delivery is calculated based on the distance traveled and the weight of waste carried. If resident i$, \forall i\in N_{PS}\cup N_{SPS}$, is assigned to waste bank $j$, then $p_{ij}=\gamma d_{ij}+\beta q_i$, where $\gamma$ and $\beta$ are multipliers for the distance traveled and waste carried, respectively. Finally, we add the information related to vehicle fixed cost $f$ and variable cost $v$ as well as the coverage area of a waste bank $\theta$ to each instance.

A real-life instance is generated based on Yogyakarta City, Indonesia. First, the locations of 55 waste banks are extracted from the city. Next, 201 locations of residents are generated randomly while considering the rationality of each location, i.e., avoiding locations that could not possibly be the residents’ locations. The remaining information is generated based on the aforementioned description. Note that the first and second sets and the real-life instance of MDWCVRPTW-SDO use Manhattan distance, while the third set of MDWCVRPTW-SDO employs Euclidean distance due to the original rule in [54].

5.2. Parameter Selection

The parameter values for our SA need to be fine-tuned in order to obtain good results. Four instances were randomly selected from the MDVRPTW benchmark instances for preliminary testing. The combinations of parameter values tested are shown in the second column of

Table 2. Parameter values tested and selected.

Parameter	Teste Values	Final Value for MDVRPTW	Final Value for MDWCVRPTW-SDO
$T_0$	5, 10, 15, 20, 50, 75, 100, 125, 150, 175, 200	10	100
$\alpha$	0.90, 0.93, 0.95, 0.97, 0.99, 0.995	0.97	0.97
$N_{non-improving}$	5, 10, 20, 30, 40, 50, 60	50	50
$I_{iter}$	2000, 3000, 4000, 5000, 6000, 7000	6000	6000
$\rho$	500, 1000, 1500, 2000, 2500, and 3000	1000	1000

. The best performing parameter values found via the preliminary testing are given in the third column of Table 2. The same parameter-tuning process is conducted for MDWCVRPTW-SDO, and the best performing parameter values are given in the last column of Table 2.

5.3. Performance of SA in Solving MDVRPTW Instances

Since MDWCVRPTW-SDO is a new problem, there are no published results for direct comparison. Therefore, we assess the performance of our SA using the published results for MDVRPTW, which is closely related to MDWCVRPTW-SDO.

Table 3. Computational results for the MDVRPTW benchmark instances.

Instance	n	d	v	BKS	Proposed SA Algorithm			Gap (%)
					Best *	Average **	Time (s)
pr01	48	4	2	1074.12	1074.121	1077.921	54.2	0.00
pr02	96	4	2	1762.21	1774.545	1790.948	260.0	0.70
pr03	144	4	2	2373.65	2396.484	2418.043	646.0	0.96
pr04	192	4	2	2815.11	2790.743	2852.746	1274.7	−0.87
pr05	240	4	2	2962.25	2996.322	3066.076	2059.2	1.15
pr06	288	4	2	3588.78	3560.857	3625.274	3058.2	−0.78
pr07	72	6	2	1418.22	1418.22	1434.091	134.9	0.00
pr08	144	6	2	2096.73	2119.179	2160.61	626.9	1.07
pr09	216	6	2	2712.56	2785.559	2835.66	1358.3	2.69
pr10	288	6	2	3464.65	3578.008	3618.99	2281.6	3.27
pr11	48	4	2	1005.73	1005.729	1015.633	66.1	0.00
pr12	96	4	2	1464.50	1466.202	1499.001	307.0	0.12
pr13	144	4	2	2001.81	2003.778	2066.783	798.8	0.10
pr14	192	4	2	2195.33	2245.461	2283.462	1544.8	2.28
pr15	240	4	2	2433.15	2477.739	2525.207	2477.3	1.83
pr16	288	4	2	2836.67	3034.587	3063.857	3468.3	6.98
pr17	72	6	2	1236.24	1240.022	1247.445	137.6	0.31
pr18	144	6	2	1788.18	1827.068	1861.81	793.0	2.17
pr19	216	6	2	2257.13	2309.472	2342.562	1681.6	2.32
pr20	288	6	2	2984.01	3126.751	3171.569	3230.1	4.78
Average							1312.9	1.45

* Best solution reported from 5 runs of SA. ** Average solution obtained from 5 runs of SA. n: number of customers. d: number of depots. v: number of vehicles available at every depot. $Gap(\%)$: $\left(Bes{t}_{SA}-BKS\right)\ast 100\mathrm{\%}/BKS$. Bold value means that SA obtains a new BKS.

presents the results obtained via SA for solving the MDVRPTW benchmark instances. The first four columns in Table 3 present the characteristics of each instance. BKS shows the best-known solutions obtained from Vidal et al. [55]. Three measurement metrics are utilized to evaluate the performance of SA: the best solution $Best$, the average solution $Average$, and the computational time $Time$ expressed in seconds (s). $Gap(\%)$ shows the comparison between BKS and the best solution obtained by SA. Based on the presented results, the worst gap obtained by SA is 6.98% with an average gap of 1.45% over all instances. Our proposed SA successfully improves two new BKSs, pr04 and pr06. The average computational time of SA for solving an instance is 1312.9 s. In conclusion, the results produced by SA are fairly good with a reasonable amount of computational time for solving MDVRPTW benchmark instances.

5.4. Performance of SA in Solving MDWCVRPTW-SDO Instances

Table 4. Computational results for MDWCVPRTW-SDO small and medium instances.

Ins	n	d	v	Gurobi		SA			Gap (%)
				Obj	Time (s)	Best	Average	Time (s)	Best	Average	Time
s1	15	4	2	129,326	47	129,326	129,326	5.2	0.00	0.00	−91.70
s2	15	4	2	68,372	22	68,372	68,372	4.4	0.00	0.00	−83.18
s3	15	4	2	67,362	12	67,362	67,362	4.2	0.00	0.00	−70.00
s4	15	4	2	128,932	17	128,932	128,932	4.9	0.00	0.00	−74.80
s5	15	4	2	128,780	92	128,780	128,780	6.8	0.00	0.00	−93.15
m1	25	6	2	71,378	12	71,378	71,378	16.9	0.00	0.00	12.50
m2	25	6	2	71,193	22	71,193	71,193	17	0.00	0.00	−30.00
m3	25	6	2	72,937	12	72,937	72,937	12.9	0.00	0.00	19.17
m4	25	6	2	71,060	433	71,060	71,060	17.4	0.00	0.00	−96.12
m5	25	6	2	71,800	18	71,800	71,800	11	0.00	0.00	−40.00
Average									0.00	0.00	−54.73

n: number of residents. d: number of waste banks. v: number of vehicles available at each waste bank. Best Gap (%): $(SA\_Best-Gurobi\_Objective)\times 100\%/Gurobi\_objective$. Average Gap (%): $(SA\_Average-Gurobi\_Objective)\times 100\%/Gurobi\_objective$. Time Gap (%): $(SA\_Time-Gurobi\_Time)\times 100\%/Gurobi\_Time$.

shows the results obtained by SA for solving MDWCVRPTW-SDO small and medium instances. As MDWCVRPTW-SDO is a new problem, we utilize Gurobi to solve the proposed mathematical model in Section 3, and the results obtained by Gurobi are used to evaluate the performance of SA. For each optimal solution provided by Gurobi, SA can also successfully obtain the optimal solution. The quality of the average solution obtained by SA for each instance is nearly optimal, showing that SA is robust for solving these MDWCVRPTW-SDO instances. In terms of computational time, SA performs 85.34% faster compared to Gurobi. We conclude that SA provides high-quality solutions with a low computational time compared to Gurobi for solving the MDWCVRPTW-SDO small and medium instances.

Table 5. Computational results for large MDWCVPRTW-SDO instances.

Instance	n	d	v		SA
				Initial	Best	Average	Time (s)
MDWCVRPTW_SDO_pr01	48	4	2	331,194.83	199,720.08	199,736.68	24.3
MDWCVRPTW_SDO_pr02	96	4	2	471,721.37	332,469.27	332,696.90	74.3
MDWCVRPTW_SDO_pr03	144	4	2	870,308.97	467,736.97	503,103.02	329.2
MDWCVRPTW_SDO_pr04	192	4	2	803,108.55	464,286.97	477,992.41	521.6
MDWCVRPTW_SDO_pr05	240	4	2	864,176.29	591,671.89	593,879.61	1192.6
MDWCVRPTW_SDO_pr06	288	4	2	682,477.53	598,975.58	643,524.65	1544.0
MDWCVRPTW_SDO_pr07	72	6	2	332,900.67	198,784.77	234,381.55	99.0
MDWCVRPTW_SDO_pr08	144	6	2	603,460.83	334,233.80	346,211.91	190.8
MDWCVRPTW_SDO_pr09	216	6	2	938,021.71	591,889.55	605,912.83	725.6
MDWCVRPTW_SDO_pr10	288	6	2	1,061,157.9	600,976.26	645,443.37	1489.3
MDWCVRPTW_SDO_pr11	48	4	2	198,322.01	133,398.76	133,426.96	42.4
MDWCVRPTW_SDO_pr12	96	4	2	464,293.91	265,079.12	265,224.42	190.8
MDWCVRPTW_SDO_pr13	144	4	2	538,058.51	331,927.92	332,424.75	376.6
MDWCVRPTW_SDO_pr14	192	4	2	599,682.84	396,890.35	397,530.05	240.8
MDWCVRPTW_SDO_pr15	240	4	2	66,1254.9	457,090.62	457,703.39	1419
MDWCVRPTW_SDO_pr16	288	4	2	1,124,544.3	588,035.03	590,577.36	1411.6
MDWCVRPTW_SDO_pr17	72	6	2	332,705.98	199,380.98	199,483.78	114.4
MDWCVRPTW_SDO_pr18	144	6	2	466,992.51	263,392.2	264,462.25	227.2
MDWCVRPTW_SDO_pr19	216	6	2	668,678.8	397,814.56	411,585.50	745.3
MDWCVRPTW_SDO_pr20	288	6	2	992,857.46	526,624.08	576,143.29	1671.6
Average				650,295.99	397,018.94	410,572.23	631.5

presents the performance of SA for solving the last set of MDWCVRPTW-SDO instances, which are generated from MDVRPTW benchmark instances. Gurobi is not utilized for solving the last set since our preliminary results indicate that Gurobi requires a significant computational time compared to SA. The first observation is that our SA significantly improves the quality of the initial solution, i.e., it improves the average quality of initial solutions from 650,295.99 to 397,018.94. The second observation is that the average quality of solutions provided by SA is reasonably robust. In particular, the average for all best solutions is 397,018.94, while the overall average of all solutions is 410,572.23. In other words, the average deviation is only 3.41%. In terms of computational time, SA averagely requires 631.52 s to solve a big instance of MDWCVRPTW-SDO. Based on these observations and the comparative results with Gurobi, we conclude that our SA provides high-quality solutions with reasonable computational times for solving MDWCVRPTW-SDO instances.

5.5. Case Study: Waste Banks in Yogyakarta City, Indonesia

This section provides insights by (1) evaluating the change in parameters in MDWCVRPTW-SDO and (2) analyzing the impact of the self-delivery option in the system, which provides managerial insights for decision makers. Sensitivity analysis is performed by using the real-life instance generated on the map of Yogyakarta City, Indonesia. Three parameters are involved and each parameter has two values (scenarios), i.e., high and low. The parameters are (1) number of waste banks (75 and 44), (2) multiplier for the distance traveled by a resident to a waste bank (0.5 and 0.3), and (3) multiplier for the load carried by a resident to a waste bank (0.5 and 0.3). In total, there are six scenarios.

Table 6. Results for changing the parameters of MDWCVRPTW-SDO real-life instances.

Scenario	Routing Cost	Compensation	Objective	Gap	${\mathit{N}}_{\mathit{F}\mathit{H}\mathit{P}}$	${\mathit{N}}_{\mathit{F}\mathit{S}\mathit{D}}$
Original	385,290	55,164	440,454	0.00	8	55
1	385,050	55,490	440,540	0.02	1	62
2	385,080	55,481	440,561	0.02	9	54
3	385,380	55,881	441,261	0.18	4	59
4	385,200	55,188	440,388	−0.01	1	62
5	386,130	68,962	455,092	3.32	5	58
6	384,810	41,931	426,741	−3.11	7	56

$N_{FHP}$: Number of flexible residents assigned as home pick-up residents. $N_{FSD}$: Number of flexible residents assigned as self-delivery residents.

contains the results obtained by changing the parameter values of MDWCVRPTW-SDO. Then, to analyze the impact of the self-delivery option, we generated another five scenarios from the real-life instances, RC-1 to RC-5, as shown in

Table 7. Five different distributions of residents of each type for the MDWCVRPTW-SDO real-life instance.

Scenario	Resident			Total Objective	Routing Cost	Compensation	Utilized Vehicles
	Type 1	Type 2	Type 3
RC-1	201	0	0	1,326,195	26,191	0	21
RC-2	67	67	67	677,570	14,400	50,377	7
RC-3	101	50	50	498,112	19,680	38,840	10
RC-4	50	101	50	382,678	14,280	58,873	5
RC-5	50	50	101	379,641	11,610	58,506	5

, each with a different distribution of resident types. SA is used to solve all scenarios, and the reported objective values are based on the best solutions obtained by SA.

For the number of waste banks (Scenarios 1 and 2), there is no significant change in the objective value, as shown in Table 6. However, from the practical point of view, the higher the number of waste banks, the higher the operational cost incurred inside the facility. Thus, the local authority needs to reconsider the appropriate number of waste banks opened in the city. In addition, when the number of waste banks is low (Scenario 3), the number of type 3 residents who perform the self-delivery option is lower compared to the original scenario. This implies that the self-delivery option is less beneficial when the number of waste banks is low. For the multipliers that determine the compensation for residents who perform the self-delivery option (Scenarios 5 and 6), the higher the multipliers are, the higher the objective values are. This phenomenon shows that the decision makers should carefully determine the compensation policy, because it will significantly affect the operational cost of MDWCVRPTW-SDO.

We are also interested in the potential benefits of introducing the self-delivery option. We suspect that the number of residents of different types will result in different magnitudes of benefits. Thus, we attempt to present potential benefits by modifying the real case instance. Table 7 shows the information related to the residents of each type for each scenario and three measurement metrics: routing cost collected from all routes, compensations collected from all residents who deliver their waste to waste banks, and number of utilized vehicles to serve the remaining residents.

Before introducing the self-delivery option, all residents must be visited within their predetermined time windows, as shown in the information of RC-1. The routing cost is the highest one among all scenarios, and the number of utilized vehicles is significantly higher compared to vehicles utilized in other scenarios. This means that, without the self-delivery option, a significantly high investment in vehicles by the local authority would be made. When the self-delivery option is introduced and four other scenarios are generated, RC-2 to RC-5, the number of utilized vehicles drops significantly. The highest number of utilized vehicles among these scenarios is 10 from RC-3. The implication shown here is that the higher the number of type 1 residents, the higher the number of vehicles required. Thus, the local authority needs to gain the interest of residents to shift from selecting the home-delivery option to either the self-delivery option or flexible delivery. We also analyze the distribution of residents of each type. Based on RC-3 to RC-5, the higher the number of type 3 residents is, the lower the total objective is. This phenomenon occurs because the flexibility of a type 3 resident is higher compared to residents of other types, resulting in a wider solution space for the system. Consequently, chances of obtaining a lower total objective are higher.

6. Conclusion and Future Research

This research introduces MDWCVRPTW-SDO as a new variant of the waste collection vehicle routing problem. A mixed integer linear programming model is formulated, and SA is developed to solve the problem. A set of newly generated instances and a real-life instance based on Yogyakarta City, Indonesia, are proposed for investigating MDWCVRPTW-SDO. The performance of SA is evaluated by solving MDVRPTW, which is a special case of MDWCVRPTW-SDO. For the MDVRPTW benchmark instances proposed by Cordeau et al. [54], the average gap between the best solutions obtained by SA and the best-known solutions is 1.45% with two new best-known solutions found. When solving the newly generated MDWCVRPTW-SDO instances, SA can obtain optimal solutions for all small and medium instances with significantly lower computational time compared to Gurobi. Moreover, SA also shows its robustness in terms of solution quality in solving the MDWCVRPTW-SDO instances. Finally, a case study obtained from Yogyakarta City, Indonesia, is provided, and we derive several insightful results for the local authorities; i.e., (1) the number of available waste banks and (2) the compensation paid to residents who select or are assigned to the self-delivery option are critical to ensure the success of the implementation. Moreover, the amount of benefits, like cost savings, obtained from implementing the self-delivery option significantly depends on the distribution of residents of each type. Thus, the challenge for the local authorities to successfully obtain benefits from the system based on MDWCVRPTW-SDO is to shift the interest of home pick-up (type 1) residents into self-delivery (type 2) or even flexible (type 3) residents.

Future research may consider heterogenous vehicles existing at every waste bank. Another interesting avenue is considering the strategic aspect of this problem, leading to a network design optimization, which may be beneficial when other regions or other countries plan to adopt a waste management system such as that defined in MDWCVRPTW-SDO. A multi-period extension can be another topic worth investigating where each resident is visited under a unique frequency and pattern. Finally, additional objectives related to social benefits or environmental concerns may be considered in future research.