This dissertation defines the operational problems of, and develops solution methodologies for, a distribution of multiple products into oil pipeline subject to delivery time-windows constraints. A multiple-product oil pipeline is a pipeline system composing of pipes, pumps, valves and storage facilities used to transport different types of liquids. Typically, products delivered by pipelines are petroleum of different grades moving either from production facilities to refineries or from refineries to distributors. Time-windows, which are generally used in logistics and scheduling areas, are incorporated in this study. The distribution of multiple products into oil pipeline subject to delivery time-windows is modeled as multicommodity network flow structure and mathematically formulated. The main focus of this dissertation is the investigation of operating issues and problem complexity of single-source pipeline problems and also providing solution methodology to compute input schedule that yields minimum total time violation from due delivery time-windows. The problem is proved to be NP-complete. The heuristic approach, a reversed-flow algorithm, is developed based on pipeline flow reversibility to compute input schedule for the pipeline problem. This algorithm is implemented in no longer than O(T*E) time. This dissertation also extends the study to examine some operating attributes and problem complexity of multiple-source pipelines. The multiple-source pipeline problem is also NP-complete. A heuristic algorithm modified from the one used in single-source pipeline problems is introduced. This algorithm can also be implemented in no longer than O(T*E) time. Computational results are presented for both methodologies on randomly generated problem sets. The computational experience indicates that reversed-flow algorithms provide good solutions in comparison with the optimal solutions. Only 25% of the problems tested were more than 30% greater than optimal values and approximately 40% of the tested problems were solved optimally by the algorithms.

No description available.

The purpose of this research is to develop a heuristic algorithm to minimize total costs in multi-commodity, multi-mode generalized networks with time windows problems. The proposed mathematical model incorporates features of the congestion of vehicle flows and time restriction of delivering commodities. The heuristic algorithm, HA, has two phases. Phase 1 provides lower and upper bounds based on Lagrangian relaxations with subgradient methods. Phase 2 applies two methods, early due date with overdue-date costs and total transportation costs, to search for an improved upper bound. Two application networks are used to test HA for small and medium-scale problems. A different number of commodities and various lengths of planning time periods are generated. Results show that HA can provide good feasible solutions within the reasonable range of optimal solutions. If optimal solutions are unknown, the average gap between lower and upper bounds is 0.0239. Minimal and maximal gaps are 0.0007 and 0.3330. If optimal solutions are known, the maximal gap between upper bounds and optimal solutions is less than 10% ranges of optimal solutions.

No description available.

When a package is shipped, the customer often requires the delivery to be made within a particular time window or by a deadline. However, meeting such time requirements is difficult, and delivery companies may not always know ahead of time which customers will need a delivery. In this thesis, we present models and solution approaches for two stochastic last-mile delivery problems in which customers have delivery time constraints and customer presence is known in advance only according to a probability distribution. Our solutions can help reduce the operational costs of delivery while improving customer service. The first problem is the probabilistic traveling salesman problem with time windows (PTSPTW). In the PTSPTW, customers have both a time window and a probability of needing a delivery on any given day. The objective is to find a pre-planned route with an expected minimum cost. We present computational results that characterize the PTSPTW solutions. We provide insights for practitioners on when solving the PTSPTW is beneficial compared to solving the deterministic analogue of the problem. The second problem is the same-day delivery problem (SDDP). The SDDP is a dynamic and stochastic pick-up and delivery problem. In the SDDP, customers make delivery requests throughout the day and vehicles are dispatched from a warehouse or brick and mortar store to serve the requests. Associated with each request is a request deadline or time window. In order to make better-informed decisions, our solution approach incorporates information about future requests into routing decisions by using a sample scenario planning approach with a consensus function. We also introduce an analytical result that identifies when it is beneficial for vehicles to wait at the depot. We present a wide range of computational experiments that demonstrate the value of our approaches.

In this study, we consider the Air Cargo Scheduling Problem based on a real life application. The aim is to move cargo and passengers that have different priorities and delivery time window, from a number of origin airports to destination airports by means of a transportation system. The system has predefined carrier routes and a heterogeneous fleet of aircraft. The problem is formulated as a heterogeneous vehicle, multi commodity, pick-up, and delivery network flow problem with a large set of system specific constraints. The proposed model determines set of movement requirements assigned on each route leg and number and type of aircraft assigned for each route in a reasonable amount of time. The model is tested with the real and generated data and the results are compared with the current methodology under different scenarios. The model produced better results in a short amount of time compared to the current methodology.

In this study we discuss the Vehicle Routing Problem with multiple use of vehicles (VRPM). In this variant of the routing problem the vehicles may replenish at any time at the depot. We present a detailed review of existing literature and propose two mathematical models to solve the VRPM. For these two models and their several variants we provide computational results based on the test problems taken from the literature. We also discuss a case study in which we are simultaneously dealing with side constraints such as time windows, working hour limits, backhaul customers and a heterogeneous vehicle fleet.

This study aims to improve transportation held between six auction centers, Inter-Auction Transportation, of FloraHolland. FloraHolland serves ninety eight percent of the Dutch market and is the largest auction in floriculture industry. The company wants to give the best sale opportunities with the costs as low as possible and this is the main initiative of this study. In this line of thought, FloraHolland wants to have a improvement on its current routing and scheduling mechanism. Exact models do not work due to the complexity and the size of the problem. Therefore, we developed a two-stage approach specific to this study. With this approach, we split exact approach into two, a mathematical model followed by a heuristic. In the exact approach, trucks are routed and scheduled at the same time. On the other hand, our solution approach first determines most efficient routes to be followed with Cycle Assignment Model and then, with Scheduling Heuristic, trucks are assigned to the routes, so within day transportation is planned in detail. Overall, each stage of this approach works in harmony and brings good solutions in a short CPU time.

This dissertation details an algorithm to solve the Intratheater Airlift Operations Problem (IAOP) using advanced tabu search. A solution to the IAOP determines the routes and assignment of customer requests to a fleet of aircraft over a given time horizon. This problem and other variants comprise an ongoing challenge for United States Air Force (USAF) planners who manage detailed logistics throughout many theaters of operations. Attributes of the IAOP include cargo time windows, multiple cargo types, multiple vehicle cargo bay configurations, vehicle capacity, route duration limits, and port capacities. The IAOP multi-criteria objective embraces several components with the primary goal of satisfying as much of the demand as possible while minimizing cost. The algorithm is extended to allow split load deliveries of customer requests, allowing a shipment to be split into two or more sub-loads which are delivered separately to the customer. The split load relaxation, while significantly increasing the complexity of the problem, allows for possible improvement in the solution. The necessary changes to the model and algorithm are detailed, providing a foundation to extend any local search algorithm solving a vehicle routing problem to allow split loading. Results allowing split loading are presented and compared with results without split loading. The algorithm is also extended to include a rolling time horizon. Starting from a solution found at a previous time step, the algorithm is limited on how the solution can be modified. This reflects the reality of operations in which near-term plans are locked as they approach and enter execution while longer-term plans are continually updated as new information arrives. / text

The Vehicle Routing Problem (VRP) is a classical problem in logistics that has been well studied by the operations research and transportation science communities. VRPs are defined as follows. Given a transportation network with a depot, a set of pickup or delivery locations, and a set of vehicles to service these locations: find a collection of routes starting and ending at the depot, such that (i) the customer's demand at a node is satisfied by exactly one vehicle, (ii) the total demand satisfied by a vehicle does not exceed its capacity, and (iii) the total distance traveled by the vehicles is minimized. This problem is especially hard to solve because of the presence of sub--tours, which can be exponential in number. In this dissertation, a special case of the VRP is considered -- where the underlying network has a tree structure (TVRP). Such tree structures are found in rural areas, river networks, assembly lines of manufacturing systems, and in networks where the customer service locations are all located off a main highway. Solution techniques for TVRPs that explicitly consider their tree structure are discussed in this dissertation. For example, TVRPs do not contain any sub-tours, thereby making it possible to develop faster solution methods. The variants that are studied in this dissertation include TVRPs with Backhauls, TVRPs with Heterogeneous Fleets, TVRPs with Duration Constraints, and TVRPs with Time Windows. Various properties and observations that hold true at optimality for these problems are discussed. Integer programming formulations and solution techniques are proposed. Additionally, heuristic methods and conditions for lower bounds are also detailed. Based on the proposed methodology, extensive computational analysis are conducted on networks of different sizes and demand distributions. / text