Service level based vehicle routing problem: Mathematical models, neural networks heuristic and operational implications

We extend the Vehicle Routing Problem (VRP) by taking the service level into consideration. The result is called the Service Level Based Vehicle Routing Problem (SLB-VRP). In this study, the service level perceived by a customer is measured by the waiting time of that customer. Three models are constructed for the SLB-VRP. Among them, two are mixed integer linear programming models that are based on the modeling of traffic flows. The third model uses decision variables that record the sequence of the customers who receive service from the vehicles and has a quadratic objective function. We have also studied how to deal with several varieties, such as the minimization of total traveled distance, the minimization of maximum waiting time, capacity constraint, and time windows.; We have developed a neural networks based heuristic to solve the SLB-VRP. The neural networks used in the heuristic are Hopfield networks. We have used a guided sampling process in the algorithm to save the computation time and estimated the maximum and minimum number of customers in a route to reduce the complexity of the networks. Two local search procedures, an oscillating procedure and a 2-opt exchanging procedure, are also implemented to improve the performance of our heuristic.; We have tested the performance of our algorithm by three approaches. The first approach is to compare our solution to an estimated optimal solution. The second approach is to compare our solution to the solutions of other well-known heuristics. The third approach is to design a performance indicator based on our solution and the statistics of the traveling distance matrix. Our experiments have shown that our algorithm has good performance according to all three approaches.; Experiments are also conducted to study the operational implications, such as the effects of the shape of the service region and the location of the depot. We have found that Circle service region has the shortest Total Waiting Time and the average Total Waiting Time in the depot at corner case is estimated to be 1.5 times of the average Total Waiting Time in the depot at center case.