Dynamic routing with competition : foundations and strategies : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Operations Research at Massey University

Operations Research studies a wide range of problems, including long-term, strategic, business planning and short-term, operational, logistical planning. Long-term business decisions revolve around the market demand for goods or services, whereas logistics focuses on efficient scheduling of production and distribution. However, vehicle routing and scheduling problems in a dynamic environment require short-term, operational planning in conjunction with computationally expensive, short-term tactical considerations. This thesis investigates a model of competition in the distribution of goods to customers, in which a number of independent carriers compete to deliver goods to a fixed set of customers. Assuming that the price and quality of the goods are consistent, each customer is indifferent towards which carrier actually delivers the required goods, but will only accept delivery from the first to arrive at their location. The main source of uncertainty is planning for competition against other independent carriers. Firstly, we consider the basic elements of competition vehicle routing and scheduling problems, and propose a Reference Model for Competition Routing Problems, synthesising the literature from vehicle routing and game theory. The general problem involves a number of independent decision makers, each representing a carrier company with a private fleet of vehicles, and a fixed set of customers to be serviced. We also formulate the Competitive Prize Collection Problem (CPCP), involving two independent decision makers with one vehicle each. The CPCP encapsulates the core elements of competition within a two player version of the Prize Collecting Travelling Salesman Problem. Secondly, we consider which strategic, tactical, and operational planning elements are important in the design of strategies for effective performance on the CPCP. We propose a Strategic Planning Architecture (SPA), i.e., a strategy framework based on hierarchical planning at nested planning horizons. This incorporates strategic and tactical planning engines based on modelling the decision problem at each planning horizon as a multiple stage game. Dynamic monitoring processes match these strategic plans to the predicted and observed movements of the opponent. Strategies which implement the SPA are designed to cover a range of planning horizons and problem sizes. A series of computational tournaments on problems of different sizes and characteristics suggests that strategies which address contingent planning, cognizance of opponent, and planning based on existing natural structure, are the most effective of those considered. In the process, benchmark sets of robust strategies, and challenging problem instances, are established against which the effectiveness of strategies may be evaluated. The significant conclusion is that for small problems, strategic considerations are more effective than routing, but for large problems, routing considerations are more effective than strategic. Problems in between require a balance between strategy, response, and routing considerations. Routing only is not sufficient; response requires good strategic information. The CPCP remains a deceptively simple problem which is computationally demanding at all scales of planning, from small problems to large problems. There is considerable scope for the study of further strategies, especially those able to classify, learn from and adapt to, the observed behaviour of the opponent, and for extrapolating these results to a richer set of competition routing problems