Solving two integrated logistical problems using Lagrangian relaxation approach

In this dissertation we study two integrated logistical models that simultaneously consider both demand selection and routing decisions in order to achieve the profit maximization objective. We first address the problem of distributing a limited amount of inventory among customers using a fleet of vehicles so as to maximize profit. Both the inventory allocation and the vehicle routing problems are important logistical decisions. National spending on these activities reached almost one hundred billion dollars last year. In many practical situations, these two decisions are closely interrelated, and therefore, require a systematic approach to take into account both activities jointly. We formulate the integrated problem as a mixed integer program and develop a Lagrangian-based procedure to generate both good upper bounds and heuristic solutions. Computational results show that the procedure is able to generate solutions with small gaps between the upper and lower bounds (2.1% on average for 20-node problems and 2.3% on average for 25-node problems) for a wide range of cost structures. Our second problem consists of selecting a set of most profitable routes for airlines that operate in long-haul markets. For these markets, the routing decision becomes critical because of the extremely large number of feasible routes arising from the relatively large number of intermediate cities covered by the operation. Moreover, the pickup-and-delivery characteristic of the problem further complicates the route selection task. Therefore, the development of an efficient procedure for selecting good candidate routes will facilitate the iterative flight scheduling process and may lead to more profitable timetables. We define an aircraft routing problem that captures the most relevant profit-generating factors in the route selection decision, formulate it as a mixed integer program, and develop a Lagrangian-based solution procedure that exploits the structure of the problem. Computational results show that the procedure is able to select a small number of good candidate routes from the fairly large number of feasible routes in each test problem, and provide good quality solutions