Period traveling salesman with customer stratification

Abstract

[ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI AT AUTHOR'S REQUEST.] The Period Traveling Salesman Problem (PTSP) has been a popular subject in the area of Traveling Salesman Problem (TSP) with the objective to minimize traveling cost over the entire M-day planning period. Most of the previous PTSP studies focused on cost minimization or vehicle capacity maximization. This research, on the other hand, looked at PTSP from a different perspective to measure the quality of customer service level. We believe customer service is the key factor to increase both profits level and customer satisfaction. We utilize the basic concepts of PTSP to develop an advanced PTSP model with customer stratification. Missouri Lottery is used as the main application in our study. The Lottery Sales Representatives (LSRs) play an important role in increasing sales by providing excellent customer service to ticker retailers throughout the state. This research is divided into two sections: (1) improve the efficiency and balance of the routing schedule of LSRs and (2) develop a new strategy to maximize customers' value functions by stratifying visit frequencies. PTSP is a generalization of TSP as an NP-hard problem; an exact solution approach would most likely to be time-consuming. Therefore, a heuristic model is developed to solve the stratification PTSP model in a reasonable amount of computation time and produces high quality solution. The first part of the research was successfully implemented to decrease the LSRs' travel distance by 15 percent, improve visitation feasibility by 46 percent, increase the balance of routes by 63 percent, and to decrease the overtime days by 32 percent. The PTSP with customer stratification has also successfully projected the improvement of 6.99 percent and 3.43 percent in the total sales values for local and remote LSRs, respectively. This research greatly benefits Missouri Lottery by maximizing customers' value functions and improving LSRs' work efficiency. This research also has a great contribution in the area of Traveling Salesman Problem in developing new efficient heuristic procedures to solve the PTSP with customer stratification model.