A case study of mutual routing–scheduling reformulation

Classical models of combinatorial problems, such as scheduling, play a key role in optimization research as they allow theoretical and empirical work to focus on core issues of problem solving performance. By their very nature, however, classical models are a simplification of real-world problems. We argue that the challenge now is to address those real-world features that were simplified away in the classical models, and that in order to do this we should investigate how problem features affect solution technologies. In this paper, we perform an empirical study of vehicle routing problems (VRPs) and job shop scheduling problems (JSPs) using commercially available constraint-based optimization software, ILOG Dispatcher, and ILOG Scheduler. We start with instances of the classical VRP and JSP and systematically make the two problems more realistic by removing the simplifying assumptions of the classical models. While doing so, we empirically investigate the key problem characteristics that make the problems more amenable to one solution technique or the other. We argue that our observations are symptomatic of the underlying technologies used in the employed software.