MODEL AND VARIABLE NEIGHBORHOOD DESCENT ALGORITHM FOR VEHICLE ROUTING PROBLEM WITH HETEROGENOUS FLEET, MULTIPLE TRIPS, MULTIPLE TIME WINDOWS, AND SIMULTANEOUS PICK-UP DELIVERY
Planning vehicle routes is one of the important decisions in the company's operational activities. The distribution of bottled water by PT. X is a vehicle route problem (VRP) with simultaneous pick-up and delivery, which means that there are delivery and pick-up activities at the customer si...
Saved in:
| Main Author: | |
|---|---|
| Format: | Theses |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/63964 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | Planning vehicle routes is one of the important decisions in the company's
operational activities. The distribution of bottled water by PT. X is a vehicle route
problem (VRP) with simultaneous pick-up and delivery, which means that there are
delivery and pick-up activities at the customer simultaneously. Departing from the
problems that occurred at PT. X, this study develop a mathematical model and
metaheuristic algorithm for the vehicle route problem with heterogeneous fleets,
multiple routes, multiple time windows, and simultaneous pick-up and delivery or
abbreviated as MRK-HRMJWMPPS.
The mathematical model developed in this study is in the form of Mixed Integer
Linear Programming (MILP) with the performance criteria of minimizing the total
transportation cost. The search for solutions using the MILP method can be done
on small-scale problems, but the computation time increases exponentially as the
amount of data increases. The Variable Neighborhood Descent (VND) algorithm
was developed to overcome the length of computation time required for the MILP
method. The search for the initial VND solution uses the Sequential Insertion (SI)
algorithm. The mathematical model and VND algorithm developed in this study can
solve the MRK-HRMJWMPPS problem, from computing the data set to produce a
feasible solution for 5 to 7 customers with a percentage difference between the
MILP and VND solutions, which is 16.88%. Data trials were also conducted with
20, 50, and 100 customers in this study using the SI and VND algorithms. The
developed model and algorithm can also be used on other MRK models, namely
MRK-RMJWPPS for limited homogeneous vehicles, MRK with multiple routes,
single time window, and simultaneous pick-up and delivery, and also for MRK-
HRMJWMPPS for mixed pick-up and delivery.
|
|---|