Heuristic Model Route Determination of Vehicle with Delivery Time Limit

Reader Impact Factor Score
[Total: 2 Average: 5]

Published on International Journal of Engineering & Industry
Publication Date: June 10, 2019

Andri Santoso, Acuk Rangga Dwi, Ivan Setiawan & Wahyu Pramana
Islam Attahiriyah University, South Jakarta
Islam Jakarta University, East Jakarta
Krisnadwipayana University, East Jakarta
Mpu Tantular University, East Jakarta
Indonesia

Journal Full Text PDF: Heuristic Model Route Determination of Vehicle with Delivery Time Limit.

Abstract
Determination of these vehicles (Vehicle Routing Problem, VRP) is a very important sub-issue of a distribution system, so it has been a lot of attention of researchers to explore the various aspects related to this issue. Basically this issue is to determine the number of vehicles with a certain capacity of transporting a commodity from one or more depots to a number of customers with the level of specific needs. The aim is to obtain the total cost or the distance or the travel time to a minimum. This paper proposed a heuristic method to resolve the question of determining the route the vehicle to a condition where every customer set limits on the start and end time of delivery, which is known as the Vehicle Routing Problem with Time Window (VRPTW). Determining the route is intended not only to minimize the total cost of travel but also the total time of the waiting customers. The amount of the costs assumed to be proportional to the distance and time.

Keywords: Vehicle routing, time window, heuristics.

1. INTRODUCTION
For companies manufacturing and services, distribution systems / transport has a very important role in providing services to consumers. To control all distribution activities and to make efficient use of system resources, the issue to be resolved can be grouped into issues that are strategic, tactical, and operational. Strategic issues related to the physical network design, determining the location of the facilities, and procurement of the necessary resources, while the tactical issues related to the allocation of existing resources to improve overall system performance.
The issue at the operational level with regard to determining the route the vehicle traveled from the depot or warehouse to a number of retailers or customers, to minimize the total cost of the trip happened. There are two models of the much-discussed operational matters to the researchers, the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP).
In the VRP models, each with a payload capacity of certain vehicles and uniforms will make the trip from depot to commodities to a number of customers with the level of specific needs, and returned to the depot. Total needs are serviced each route does not exceed the carrying capacity of the vehicle. Every customer is only served by one vehicle and each delivery route should only be visited every customer one time. The aim is that each customer needs are met with the minimum total cost.
If enacted certain time limit, either a time limit for the vehicle departs from and returns to the depot and when the fastest and slowest for the vehicle to arrive at each of its customers, the problem is known as the Vehicle Routing Problem with Time Window (VRPTW). In this VRPTW models to be solved not only determine the route but also the scheduled departure time of each vehicle to minimize the total cost of the trip and total customer wait time.

2. PURPOSES
Although the question of involving the VRP models encountered in everyday life, but to obtain the optimal solution is not easy because of the VRP is NP-hard problem, Solomon [1].
This has motivated researchers to develop various heuristic methods that can be used to solve problems in everyday life, which are generally large, Solomon [2] ,, Thangiah [3], Ioannou [4].
On This paper presents a heuristic method to solve the problem VRPTW, using methods Insertion Heuristic-I1 as the basis for development. Insertion Heuristic Method-I1 itself is essentially a development of the Saving Heuristic method developed by Clarke and Wright’s classic VRP issues, Ghiani [5]. Item 3 of this paper outlines the issues to be resolved formulations as well as mathematical models, heuristic methods discussed was presented in item 4.
To facilitate understanding of the methods discussed, in point 5 is presented a numerical illustration complete with the calculation results. As the closing of the entire discussion, in point 6 raised several issues related to the heuristic method are discussed.

3. FORMULATION ISSUES
To explain VRPTW models, consider a graph (N, A). Set node N comprises a set of customers, expressed as C, where node 0 and node n + 1 is the depot. Set arc A represents the relationship between a single node with other nodes. No arc ending at node 0 and no arc that starts from the node n + 1. Each route will begin from node 0 and will end at the node n + 1. Each arc (i, j) A characterized by Cij costs and travel time TIJ.
Because in the costs considered proportional to the distance and time, the amount of unit costs can be declared equal to 1. Each customer is related to the needs and the service time ti, iC, Set the vehicle is expressed as V where each vehicle has a transport capacity of the uniform, that is q. Service in every customer must be implemented within the time interval [ai, bi], i C, Each vehicle must leave the depot in the time interval [a0, b0] and must be returned to the depot in the time interval [an + 1, bn + 1]. Vehicles that arrive at the customer prior to the start time window must wait until the service can be started, but it should not come after the upper limit of the time window.
The objective function (1) states that the total costs should be minimized. Divider (2) states that every customer is only served by one vehicle, while limiting (3) states that every vehicle will only serve consumers limited capacity. Delimiter (4), (5) and (6) states that any vehicle k will depart from the depot, leaving the node h, (hC) If the vehicle enters the node h, and will return to the depot. Arc (0, n + 1) is inserted into the network to include the initial trip from the depot and travels back to the depot. Delimiter (7) states that if the vehicle k traveling from i to j then tesebut vehicle will arrive at node j after , Divider (8) states that every vehicle will arrive at the customer k i within the time window of the customer, while the barrier (9) is limiting integralitas.

4. RESULTS AND DISCUSSION
Heuristic method discussed in this paper is essentially a service establishment procedure is done by selecting the customer (expressed as nodes) to be inserted into an existing route. The insertion process is done until a route is concerned expressed “full”, both based on the capacity of the vehicle as well as a time schedule of service at each customer. The aim is to establish one or more of these services with the minimum total travel expenses. Assumed in the costs proportionate to the distance and time.
The process of selecting and inserting the node into the route is done as follows:
Step 0 (Initialization)
o Declare all of the nodes (excluding the depot) is not entered in the route as a free node
o Select a node is free to be used as the initial node of the route to be set up, such as the state node node i. Selection of the start node can be based on the distance of the node to the depot or on the basis of service time schedule.
o Set the initial service as R = {0, i, n + 1} with 0 and n + 1 is a depot
Step 1 (Setting of the parameter)
o State the free nodes are considered to be inserted as a node u
o Set the value of the parameter μ is the weight given to saving the distance obtained if u do the insertion node. μ ≥ 0
o Set the value of the parameter α1 is the weight given to the total distance that occurs due to the insertion node u and parameter α2 ie the weight given to the change of service time due to the insertion node u. α1 + α2 = 1
o Set the value of the parameter λ is the weight given to the cost of travel from the depot to node u if node u is not inserted into the route. λ ≥ 0
Step 2 (Selection and insertion node)
o State the current route as R = {0, i1, …, j} (0 and j is the depot)
o For each free node u, calculate the total extra distance that occurs when a node u pasted, by using the Z11 formula (i, u, j) = diu + DUJ – μ dij;
μ ≥ 0; diu, DUJ, and each dij is the distance between node i to node u, u node to node j, and node i to node j
o Calculate the additional time for the vehicle to arrive and start the service at node i if node u pasted, by using the formula
Z12 (I, u, j) = T0u + tu + tui – t0i
t0u, tui, and t0i is the travel time from depot to node u, from node u to node i, and from depot to node i, while tu is the time of service at node u
o Calculate the amount of costs which is proportional to the insertion of additional extra distance and travel time to arrive at the node i if node u pasted, by using the formula
Z1 (I, u, j) = α1 Z11 (I, u, j)
+ α2 Z12 (I, u, j); α1 ≥ 0;
α2 ≥ 0; α1 + α2 = 1
o Insert free node u that has a value Z1 (i, u, j) minimum to the route, between nodes i and j existing node
o If the capacity of the vehicle and the service time limit still memungkin- right, do the following insertion based on the value Z2 (i, u, j) the maximum, where
Z2 (I, u, j)= Λ d0u – Z1 (i, u, j); λ ≥ 0
stating the difference between the costs that occur when a node u are taken directly from the depot at a cost that occurs when a node u is inserted into the
Step 3 (Repetition)
If there is still a free node, repeat steps 2 through the entire node into the route.
Step 4 (Repair solution)
For each service that has been established, make changes to the position or sequence of nodes visited customers, to obtain the total distance and total waiting time to a minimum.

5. NUMERICAL ILLUSTRATION
Suppose there is a depot that serves the delivery of a commodity to 12 customers. In Table 1 are presented data rate needs of commodities (in units) and a time schedule of service at each customer. Data distance (in km) and travel time (in minutes) from the depot to customers and between customers is shown in Table 2. The capacity of each vehicle is 30 units, while long-time service in every customer is 15 minutes. Each vehicle must leave the depot at 9:00 pm and must be returned to the depot at 12:00.

Table 1. Data rate needs and schedule of service

Table 2. Data range (below diagonal) and travel time (above diagonal)

To resolve the above issues stipulated value of μ = 1; α1 = α2 = 0.5; and λ = 1. From the above data it is known that the total demand across the customer is 84 units. Because the vehicle capacity is 30 units would require three units of the vehicle, which means it will also form three routes originating and ending at the depot.

Iteration 1:
As an initial node on the route R1 selected node 9 which is a customer with an initial limit and the deadline for the fastest service, so that R1 = {0, 9, 0}. Due to the capacity of the vehicle and the service time schedule still allows the election next node u to be inserted. Results of the calculations are presented in Table 3.
Based on the value of the node Z1 should disispkan between node 9 and the depot is the node 8 to obtain route R1 = {0, 9, 8, 0}. The insertion process can still be done with regard to the value Z2 and eventually obtained the R1 = {0, 9, 8, 10, 12, 0}.
Resume results of these calculations for R1 are presented in Table 4.

Table 3. Results Calculation for Iteration 1.
Table 4. Resume Calculation Results Iteration 1.

In the same way do the calculations to obtain the second and third route in order to obtain R2 = {0, 1, 4, 5, 2, 0} and R3 = {0, 3, 6, 7, 11, 0}. The second route is not feasible because it causes the vehicle to arrive at the depot more than 12:00.
This happens because of the waiting time R2 obtained for 70 minutes at 4 customers, while R3 obtained from these waiting times for 54 minutes in customers 6. Therefore, the evaluation of customer service order to obtain a new service feasible.
The results obtained are R2 = {0, 1, 5, 2, 4, 0} and R3 = {0, 3, 7, 11, 6, 0}. Resume calculation results are presented in Table 5 and Table 6.

Table 5. I Resume Calculation Result

Table 6. I Resume Calculation Result

6. CONCLUSION
Pendisribusian a commodity from the depot or warehouse to a number of agents or customers is another common problem encountered in everyday life, as well as a problem that is not easily solved using optimization models. Because it is necessary to develop a method of settlement that is simple and easy to do, but it can provide a solution that is close to the optimal solution.
Heuristic method discussed in this paper uses a simple formula that can be easily resolved manually, although for large-sized problems. Due to the obtained solution will be determined by the value of the parameters μ, α1, α2, and λ is used it to obtain the best solution (based on defined criteria) should be repeated calculations with different values for each parameter. If the amount of expenses not assumed to be proportional to the distance and time it is on the electoral process node to be inserted (step 2), the value of Z11 (i, u, j) and Z12 (i, u, j) to be multiplied by the unit costs applicable. Likewise, the (λ d0u) must be multiplied by unit costs prevailing prior to calculating the value Z2 (i, u, j).