The Missouri lottery optimizes its scheduling and routing to improve efficiency and balance

The Missouri lottery, a profit-driven nonprofit organization, generates annual revenues of over $800 million by selling lottery tickets; 27.5 percent of the revenue goes to Missouri's public education programs. The lottery sales representatives (LSRs) play a central role in increasing sales by providing excellent customer service to ticket retailers throughout the state. Hence, LSRs must have equitable, balanced work schedules and efficient routes and navigation sequences. Our objective was to provide scheduling and routing policies that minimize LSRs' total travel distance while balancing their workloads and meeting visitation constraints. We modeled the problem as a periodic traveling-salesman problem and developed improvement algorithms specifically to solve this problem. The newly implemented schedules and routes decrease the LSRs' travel distance by 15 percent, improve visitation feasibility by 46 percent, increase the balance of routes by 63 percent, decrease overtime days by 32 percent, and indirectly increase the sales of lottery tickets by improving customer service.