Only 14 pages are availabe for public view
The Vehicle Routing Problem (VRP) is one of the most detailed problems in the Supply Chain area as it requires detailed information about the travel times and routing sequence. Many efforts were made to solve optimally the VRP under various configurations. However, due to the combinatorial nature of the problem, as it is proven to be NP-Hard problem, reaching optimal solution is not an easy task. Efforts are diverted to heuristic techniques and algorithms, looking for reaching near optimal solutions, besides that, they can easily be applied. Most of the developed heuristics and algorithms targeted the traditional VRP, in which, the distance travelled is minimized. Much less work was done to consider the role of integrating different decisions on determining such routes, such as the inventory and location decisions. In the present work, the traditional Inventory Location Routing Problem (ILRP) and the Inventory Location Routing Problem while applying the Vendor Managed Inventory (VMI) policy are considered. This is concerned with determining the depots to use, the dispatching times and routing of the vehicles and quantities to deliver to a given set of customers that need continuous constant demand rates of a number of products.
In an Inventory Location Routing Problem (ILRP), decisions about the inventory at the depots or customers, locations of the depots to use, are to be taken as well as the routing decisions. A set of customers need to be visited every period with equal delivery quantities; in order to meet continuous stationary demand rates of a set of products. This is typically done in repetitive routes every period with the same dispatching times from the different depots, and arrival times at each customer. The objective is to determine the dispatching times and routes of the vehicles and the depots to use during the period.
In the ILRP with VMI policy, a set of customers have to be visited to have equal delivery quantities in repetitive periods; in order to meet stationary continuous demand rates. Each customer has a certain period, over which, it is re-visited. The period is an integer of a basic period, which may differ from one customer to another. This integer is determined using a heuristic that depends on the holding cost, distance from the nearest depot, as well as the demand rate. The allocation of products to the different basic periods uses another heuristic, that depends on the delivery quantities to the different customers and the total quantities assigned to be delivered within the different periods; in order to obtain close distribution of quantities over the periods, hence close numbers of vehicles dispatched.
The purpose of this research is to solve a traditional ILRP and an ILRP with VMI having multiple products. Each customer is assumed to have equal deliveries of sufficient quantities; to satisfy the demand of the products, until it is re-visited in a following period. The travel times of the arcs, as well as the demand rates are known and constant. A limited number of homogeneous capacitated vehicles is available at each depot. Any vehicle can be dispatched from the corresponding depot, and should return to the same depot before the end of the period, without being able to wait at any customer. No shortage is allowed at any customer. Batch splitting is prohibited. The objective is to find the delivery quantities, allocate customers to the different periods, select the depots to use in each period, determine the dispatching times and routes of the vehicles selected to be dispatched; in order to minimize the total cost.
The total cost consists of the transportation costs, the vehicles’ dispatching costs, routing costs, and holding costs at the depots and customers. Transportation cost is considered whenever a depot is to be used in a period, as the delivery quantities that have to be delivered within the period should be received at the depot before the start of the period. Delivery quantities are shipped from the factory to the depot, and a transportation cost is incurred regardless of the quantity shipped. Dispatching cost is due whenever a vehicle is dispatched. Routing cost represents the cost of traversing the arcs, that is proportional to the distance travelled. Holding cost at the depots consider the delivery quantities that are available at the depot from the start of the period until they are loaded on the vehicles to be distributed. During that time, holding cost is incurred. Lastly, the holding cost at the customer is charged by the supply chain if the customer is to be visited every certain number of the basic period. In that case, the supply chain is charged for the holding cost for keeping the products for more than one basic period. No cost is charged for placing orders.
To deal with multiple products, the model is formulated at the beginning for a single product, then it is generalised to deal with multiple products. The same approach is followed in the solution methodology. To allocate customers to the different periods, the customer-multiplier, customer-allocation delivery strategy is followed. Under some conditions, the customer-multiplier, customer-allocation can be transformed to an equivalent single-product problem.
In literature, there are many algorithms that were developed to solve the ILRP. However, research in the field of the ILRP was given little attention as compared to that given to the VRP. One of the algorithms which proved to be superior in determining a near optimal solution in general, and the VRP in particular, is the Genetic Algorithms (GAs). The governing factors of the performance of the GA are the crossover and mutation operators, the population size and the crossover rate. Many crossover and mutation operators were developed to suit the VRP. The GA is not widely used in solving the ILRP due to the difficulty of forming a chromosome containing the different decisions considered.
As previously mentioned, the VRP in general is considered NP-hard problem due to its combinatorial nature. In order to solve such problem, GA is used, where the total cost is the fitness function and the chromosome consists of two parts. The first part represents the dispatching times of the vehicles (as represented by the fraction of the feasible dispatching time), and the other part represents the routing of the different vehicles. The dispatching time is represented as fractional numbers between zero and one, while the sequence part is represented by a three-dimensional array; to represent the route of each vehicle dispatched from each depot in each period. The crossover operator is Two-Points crossover for the binary form of the dispatching times’ part and a newly developed Best Route Best Feasible Insertion crossover for the routing part. The mutation operator is Inversion for the binary form of the dispatching times, and a newly developed Best/Worst Insertion of Random Number of Worst/Best Routes mutation for the routing part. The Population Size is 20, the Crossover Fraction is 0.8, the number of elite children for each generation is one, and the total number of generations is 500. A heuristic stage is performed on the population every five generations. The initial population is generated randomly using a newly developed heuristic, and the selection function is stochastic uniform.
Introducing the improvement heuristics to improve the proposed GAs is checked in the first set of experiments. Three approaches are investigated in this set, while applying the GAs. The first applies the three improvement heuristics altogether, while the second approach applies the three heuristics in a stepped manner. The third approach applies the previous two approaches and selects the best solution out of both of them. selecting the frequency of applying the improvement heuristics along the application of the GAs is another aim of the first set of experiments. The results are compared, based on the average saving percentage in the obtained total cost, as well as the solution time.
In order to understand the effect of changing the decision variables in the succeeding experiments on the objective function of minimising the total cost as well as the performance measures, the second set of experiments is designed. The decision variable to be investigated are the dispatching times of the vehicles, their routing, the depots to use, the allocation of the customers to the basic periods, and the period multipliers of the customers. The performance measures studied are: the average number of opened depots per period, the average number of dispatched vehicles per period, the average total distance travelled per period, the average utilization of the vehicles, and the number of periods within the repeated period.
The third set of experiments is designed to study the effect of different parameters on the different cost elements, while minimizing the total cost, for the best reached solutions of both the ILRP with VMI and the traditional ILRP approaches, and compare both approaches. The effect of the parameters is also investigated on the number of opened depots, the number of dispatched vehicles, the average total distance travelled per period, as well as the average utilization of the vehicles. The parameters under investigation are the transportation cost, vehicle dispatching cost, travel cost per unit travel time, unit inventory holding cost at the depots, and at the customers, number of available vehicles per depot, and the vehicle capacity.
Finally, studying the performance of the different delivery strategies of the multi-product ILRP is possible through the fourth set of experiments. Two products are considered, whose unit inventory holding costs ratio at the customers and demand rates ratio are changed, while minimizing the total cost; to study their effect on the average total cost per period, and the performance measures, for each delivery strategy.
The model has proven to be able to solve the ILRP considered with the different cases studied. The ILRP with VMI proved to be superior to the traditional ILRP especially with high travel cost per unit distance and low unit inventory holding cost at the customers, as well as far customers from the depots. The equivalent single-product model showed its superiority in the computational time. Yet, the customer-multiplier, customer-allocation delivery strategy showed to have the lowest average total cost per period.