Science and Technology Indonesia e-ISSN:2580-4391 p-ISSN:2580-4405 Vol.
No.
April 2021 Research Paper Heuristic Approach For Robust Counterpart Open Capacitated Vehicle Routing Problem With Time Windows Evi Yuliza1 .
Fitri Maya Puspita1 *.
Siti Suzlin Supadi2 1 Mathematics Department.
Faculty of Mathematics and Natural Science.
University of Sriwijaya.
South Sumatera.
Indonesia 2 Institute of Mathematical Sciences.
Faculty of Science.
University of Malaya.
Malaysia *Corresponding author: fitrimayapuspita@unsri.
Abstract Garbage is one of the environmental problems.
The process of transporting garbage sometimes occurs delays such as congestion and engine failure.
Robust optimization model called a robust counterpart open capacitated vehicle routing problem (RCOCVRP) with time windows was formulated to get over this delays.
This model has formulated with the limitation of vehicle capacity and time windows with an uncertainty of waste volume and travel time.
The RCOCVRP model with time windows is solved by a heuristic approach.
The heuristic approach used to solve the RCOCVRP model with time windows uses the nearest neighbor and the cheapest insertion heuristic algorithm.
The RCOCVRP with time windows model is implemented on the problem of transporting waste in Sako sub-district.
The solutions of these two heuristic approaches are compared and analyzed.
The RCOCVRP model with time windows to optimize the route problems of waste transport vehicles that is solved using the cheapest insertion heuristics algorithm is more effective than the nearest neighbor method.
Keywords Optimization Robust.
Counterpart Open Capacitated Vehicle Routing Problem.
Time Windows.
Nearest Neighbour Algorithm.
Cheapest Insertion Heuristic Algorithm Received: 14 November 2020.
Accepted: 23 March 2021 https://doi.
org/10.
26554/sti.
INTRODUCTION
Garbage is one of the environmental problems.
To solve this environmental problem, the department of cleanliness and the environment carries out waste transportation activities.
Garbage transport vehicles carry garbage to a temporary dump site (TDS) and end up at the final disposal site (FDS).
Classic vehicle routing problem, also known as capacitated vehicle routing problem, has the characteristic that the vehicle departs from the starting point and returns to the starting point for example the route of the vehicle on the distribution of LPG gas (Yuliza and Puspita, 2.
The route of the waste transportation vehicle is an open vehicle routing problem (OVRP) that the garbage transporting vehicle transports waste from the TDS and then takes it to the FDS.
The process of transporting garbage sometimes occurs with delay, such as congestion and equipment failure.
Robust optimization is an optimization problem approach for data that has uncertainty.
De La Vega et al.
, 2019 formulated an optimization model for the robust vehicle routing problem (RVRP) with time windows and multiple deliverymen.
Sungur et al.
, 2008 and Sun and Wang, 2015 discuss robust optimization of the vehicle route problem with many uncertain requests.
Ro- bust optimization research has experienced developments in the problem of vehicle routes, for example in the transportation and logistics sectors The robust capacitated vehicle routing problem (RCVRP) model is a robust optimization that takes into account the uncertainty of demand to minimize the cost of shipping products to costumers (Gounaris et al.
, 2.
Robust vehicle routing problem with time windows (RVRPTW) is a robust optimization that takes time windows into account.
Agra et al.
, 2013
discussed RVRPTW on transportation problems where delays often occur so that the travel time is uncertain.
Braaten et al.
2017 investigated the limit of the maximum amount of delay in the RVRPTW model and this model was solved by a heuristic method based on a large adaptive neighborhood search.
Hartono et al.
, 2018 proposed a robust counterpart vehicle routing problem (RCOCVRP) model for waste transportation by request using the branch and bound algorithm.
Puspita et al.
, 2018a discussed the RCOCVRP model on the problem of waste transportation in Sako and Sukarami Districts.
Puspita et al.
, 2018b discussed the RCOCVRP model with a request on the problem of waste transportation in Sematang Borang District.
Research on the problem of solid waste collection and robust Science and Technology Indonesia, 6 .
53-57 Yuliza.
E et.
optimization models has been widely studied (Buhrkal et al.
Campos and Arroyo, 2016.
Hannan et al.
, 2018.
Nguyen et al.
, 2013.
Perea et al.
, 2016 ).
Hartono et al.
, 2018.
Puspita et al.
2018b discuss the robust counterpart open capacitated vehicle routing problem (RC-OCVRP) model.
Puspita et al.
, 2018a discussed the robust demand counterpart open capacitated vehicle routing problem (DR-CVRP) model on the problem of waste transportation routes.
This research discusses the optimization modeling of robust counterpart open capacitated vehicle routing problem (RCOCVRP) with soft time windows, which means that the arrival time of the vehicle in a TDS .
r in FDS) can be equal to or more than the final time.
Yuliza et al.
, 2020b has proposed the RCOCVRP model with time windows on the problem of transporting garbage This model is solved with an exact approach.
The RCOCVRP model with time windows is solved by the cheapest insertion heuristics algorithm then solved using the GAMS software (Yuliza et al.
, 2.
RCOCVRP model with time windows produces optimal results solution by considering the volume of waste in each TDS carried by the vehicle does not exceed the vehicle capacity, and travel time does not exceed the time of arrival of the vehicle and solved using the nearest neighbor method (Yuliza et al.
, 2020.
This model is formulated with the limitation of vehicle capacity .
cE) and time windows .
with uncertainty of travel time .
cycn y.
and volume of waste .
cycn ).
In this case, the vehicle arriving at a TDS or FDS may exceed the time windows.
The RCOCVRP model with soft time windows is applied to the garbage transportation route in Sako District.
Palembang.
Time windows can be viewed as the time interval from the time the vehicle departs and the time the vehicle arrives at a customer (Agra et al.
, 2.
This model aims to optimize the route of the waste transport vehicle so as to minimize the distance.
This model is solved by a heuristic approach.
The heuristic approach used to solve the RCOCVRP model with soft time windows uses the nearest neighbor and the cheapest insertion heuristic algorithm.
The nearest neighbor algorithm and the cheapest insertion heuristics algorithm have the same working principle, namely finding the closest point from the initial point.
EXPERIMENTAL SECTION
1 Materials Primary data in the form of the names of TDS and FDS, vehicle capacity, time windows and service time were obtained through direct interviews with the environmental and sanitation department.
Secondary data in the form of distance between each TDS to TDS and FDS and travel time are obtained from the google maps application.
Each sub-district has a TDS as a temporary disposal site for waste transported by the department of cleanliness and the environment waste collection vehicles with uncertain waste volume.
The type of vehicle for each work area is a dump The garbage collection vehicle in Sako sub-district has 3 working areas.
The garbage collection vehicles serve several TDS in work area 1, work area 2 and work area 3, respectively.
A 2021 The Authors.
Table 1.
Time windows and waste volume in working area 1 Time Windows Volume of waste .
07:00, 07:30 07:30, 08:00 08:00, 08:30 08:30, 09:00 09:00, 09:30 09:30, 10:00 10:00, 11:00 q1 =800 q2 =1500 q3 =600 q4 =4000 q5 =700 q6 =2000 q7 =6000 as many as 6 TDS, 4 TDS and 11 TDS.
Sako district is a densely populated residential area, so the problem of transporting waste is a concern.
RCOCVRP model with time windows is simulated on the route of garbage collection vehicles in the working area Time windows and waste volume in working area 1 is shown in Table 1.
The distance between TDS i to TDS j and the distance of each TDS to FDS are expressed in the distance matrix as shown in Table 2.
It is assumed that the waste transport vehicle has an average speed of 40 km/hour.
Based on the results of interviews with officers in the environmental and sanitation department, the average service time is around 15 minutes.
2 Methods Due to their greedy nature, sometimes the nearest neighbor algorithm can skip a shorter route.
However, the nearest neighbor is easy to implement and up quickly (Pop et al.
, 2.
The cheapest insertion heuristics algorithm is able to solve the problem of vehicle routes.
In the case of waste transport routes, each TDS is represented as a point and the travelling from TDS i to TDS j can be represented as an arc.
1 Nearest Neighbor Algorithm Following are the steps of the nearest neighbor algorithm for the problem of transporting waste: Step 1: Find the closest distance to each TDS from the initial TDS as the starting node.
Step 2:
Find the closest node from the starting node provided that the garbage volume from each TDS does not exceed vehicle capacity.
Step 3: If the garbage volume exceeds the vehicle then start again from Step 1.
Step 4: Repeat step 2 until all TDS .
ncluded FDS) are visited.
2 Cheapest Sequential Insertion Algorithm The principle of the cheapest sequential insertion algorithm is to make the initial route first.
Starting from arc .
cn, y.
from the starting vertex to the destination vertex and try to insert vertex k at a certain position gives the best criteria (Alatartsev et al.
Scutelly, 2.
The arc .
, .
with which node k is inserted is calculated using the formula in the following formula:
ycaycnyco ycaycoyc Oe ycaycnyc Page 54 of 57 Science and Technology Indonesia, 6 .
53-57 Yuliza.
E et.
Table 2.
Matrix of distance .
TDS1
TDS2
TDS3
TDS4
TDS5
TDS6
FDS
TDS1
TDS2
TDS3
TDS4
TDS5
TDS6
FDS
lated as Equation 2.
subject to Table 3.
Variables Variables Description xycnyc yycn tycn the vehicle traveling from TDS i to TDS j vehicle load when leaving TDS i.
arrival time to TDS i If none of the arcs provide the best criteria then form a new This process is repeated until all nodes are selected.
RESULTS AND DISCUSSION
Given a directed graph ya = .
cO , y.
where ycO = .
, 2, 3, .
, ycu .
as the set of nodes and A={.
O i=1,2,.
,n 1 } dan yc = .
, 2, .
, ycu 1, ycn O y.
as a set of arcs, where nodes 1, 2, .
, ycu represent each TDS and node ycu 1 represents FDS.
Denoted ycA with ycA OC ycO as a set of nodes that do not start from an origin .
and destination .
The set ycN represents the set of all time windows for each node T=.
caycn , ycaycn O i OO V} .
The set yceycuyc.
cN ) represents all the extreme points on T.
The variables and parameters proposed is the following:
The RCOCVRP with time windows in working area 1 is formulated as follows:
Minimize 4ycu12 0.
4ycu21 55ycu23 0.
55ycu32 1ycu34 1.
1ycu43 7ycu45 4.
7ycu54 8ycu56 1.
6ycu65 6ycu67 2.
Based on the data in Table 1 and Table 2, the RCOCVRP model with time windows aims to minimize the distance traveled by waste transport vehicles so that the objective function is formu- ycu12 ycu13 ycu14 ycu15 ycu16 ycu17 = 1, ycu21 ycu23 ycu24 ycu25 ycu26 ycu27 = 1, ycu31 ycu32 ycu34 ycu35 ycu36 ycu37 = 1, ycu41 ycu42 ycu43 ycu45 ycu46 ycu47 = 1, ycu51 ycu52 ycu53 ycu54 ycu56 ycu57 = 1, ycu61 ycu62 ycu63 ycu64 ycu65 ycu67 = 1, ycu71 ycu72 ycu73 ycu74 ycu75 ycu76 = 1 Garbage transport vehicles visit each node only as Constraints .
is defined as at least one trip by a waste transport vehicle from node ycn to node yc and at least one trip by a waste transport vehicle from node yc to node ycn.
ycu21 ycu31 ycu41 ycu51 ycu61 ycu71 Oe ycu12 Oe ycu13 Oe ycu14 Oe ycu15 Oe ycu16 Oe ycu17 = Oe1.
ycu17 ycu27 ycu37 ycu47 ycu57 ycu67 Oe ycu71 Oe ycu72 Oe ycu73 Oe ycu74 Oe ycu75 Oe ycu76 = 1.
ycu12 ycu32 ycu42 ycu52 ycu62 ycu72 Oe ycu21 Oe ycu23 Oe ycu24 Oe ycu25 Oe ycu25 Oe ycu27 = 0.
ycu13 ycu23 ycu43 ycu53 ycu63 ycu73 Oe ycu31 Oe ycu32 Oe ycu34 Oe ycu35 Oe ycu36 Oe ycu37 = 0.
ycu14 ycu24 ycu34 ycu54 ycu64 ycu74 Oe ycu41 Oe ycu42 Oe ycu43 Oe ycu45 Oe ycu46 Oe ycu47 = 0.
ycu15 ycu25 ycu35 ycu45 ycu65 ycu75 Oe ycu51 Oe ycu52 Oe ycu53 Oe ycu54 Oe ycu56 Oe ycu57 = 0.
ycu16 ycu26 ycu36 ycu46 ycu56 ycu76 Oe ycu61 Oe ycu62 Oe ycu64 Oe ycu64 Oe ycu65 Oe ycu67 67 = 0 Constraints .
ensure that no sub-tours are cut off for each node visited by the garbage transport vehicle and the vehicles traveling from TDS ycn to TDS yc are the same as vehicles from TDS yc to TDS ycn.
800 O yc1 O 8000, 1500 O yc2 O 8000, 600 O yc3 O 8000, 4000 O yc4
O 8000
700 O yc5 O 8000, 2000 O yc6 O 8000, 0 O yc7 O 8000 Constraint .
states that the load of waste transport vehicles is limited by the volume of waste and the capacity of the vehicle.
yc1 Oe yc2 8000ycu12 O 4500, yc2 Oe yc3 8000ycu23 O 5400, yc3 Oe yc4 8000ycu34 O 2000, yc4 Oe yc5 8000ycu45 O 5300, yc5 Oe yc6 8000ycu56 O 4000, yc6 Oe yc7 8000ycu37 O 0 A 2021 The Authors.
Page 55 of 57 Science and Technology Indonesia, 6 .
53-57 Yuliza.
E et.
Table 4.
Parameters Parameters Description cycnyc qycn tycnyc aycn byc distance between TDS i to TDS j and the distance of each TDS to FDS load of waste transport vehicles travel time from TDS i to TDS j.
departure time from TDS i vehicle arrival time at TDS j Table 5.
The solution of the RCOCVRP model with time windows in working area 1 Nearest neighbor algorithm Cheapest insertion Heuristic algorithm Route Distance .
TDS 1 Ae TDS 3 Ae TDS 2 Ae FDS TDS 4 Ae TDS 5 Ae FDS TDS 6 Ae FDS TDS 1 Ae TDS 2 Ae TDS 3 Ae FDS TDS 4 Ae TDS 5 Ae FDS TDS 6 Ae FDS The volume of waste is uncertain so that the load of garbage vehicles at each node is formulated as Constraints .
7 O yc1 O 7.
5, 7.
5 O yc2 O 8, 8 O yc3 O 8.
5, 8.
5 O yc4 O 9, 9 O yc5 O 9.
5 O yc6 O 10.
5, 10.
5 O yc7 O 11, .
The vehicle travel time when visiting node i is limited by the time windows formulated by Constraints .
yc1 Oe yc2 0.
01ycu12 O 0, yc2 Oe yc3 0.
01375ycu23 O 0, yc3 Oe yc4 0.
0275ycu34 O 0, yc4 Oe yc5 0.
0425ycu45 O 0, yc5 Oe yc6 0.
145ycu56 O 0, yc6 Oe yc7 0.
ycu67 O 0 Vehicle arrival time at node ycn is influenced by departure time, travel time and vehicle arrival time at node yc formulated by Constraints .
The calculation of the RCOCVRP model with time windows is solved by the Nearest Neighbor algorithm simulated in the working area 1.
Furthermore, the calculation of the RCOCVRP model with time windows is solved by the cheapest insertion heuristic algorithm.
The route of waste transport vehicles in working area 1 uses the nearest neighbor algorithm and the cheapest insertion heuristics algorithm is shown in Table 5.
The total distance of waste transport vehicles in working area 1, respectively, using the nearest neighbor method and the cheapest insertion heuristic algorithm are 11.
65 km and 11.
The results of calculations using these two heuristic approaches are almost the same.
This is influenced by the working principle of these two heuristic approaches is to find the closest The results for working area 2 and working area 3 use the nearest neighbor algorithm and the cheapest insertion heuristics algorithm as shown in Table 6.
A 2021 The Authors.
Based on Table 5 and Table 6, it is obtained that the total distance of waste transport vehicles in Sako sub-district using the nearest neighbor algorithm is 54.
29 km and the total distance traveled using the cheapest insert heuristic algorithm is 54.
The RCOCVRP model with time windows to optimize the route problems of waste transport vehicles that is solved using the cheapest insertion heuristics algorithm is more effective than the nearest neighbor method.
The basic principle of the nearest neighbor method is to find the minimum distance from each arc .
cn, y.
The cheapest insertion heuristic algorithm inserts each node k on arc .
cn, y.
Then find the minimum distance between the two insertion arcs so that the node not visited can be avoided.
CONCLUSIONS
RCOCVRP with time windows can be used to solve waste transportation route problems.
The results of the calculation of this model using the nearest neighbor method and the cheapest insertion heuristics algorithm produce almost the same solution because the principle of these two heuristic approaches is to find the closest distance.
the cheapest insertion heuristics algorithm is more efficient than the nearest neighbor algorithm for determining the route of the waste transport vehicle.
From the calculation results, it is found that the cheapest insertion heuristic algorithm is more efficient than the nearest neighbor algorithm for determining the route of the waste transport vehicle.
REFERENCES