Realistic two-stage flowshop batch scheduling problems with transportation capacity and times

This paper investigates single-batch and batch-single flow shop scheduling problem taking transportation among machines into account. Both transportation capacity and transportation times are explicitly considered. While the single processing machine processes one job at a time, the batch processing machine processes a batch of jobs simultaneously. The batch processing time is the longest processing times of jobs assigned to that batch.Each problem is formulated as a mixed integer programming model to find optimal makespan. Lower bounds and heuristic algorithms are proposed and computational experiments are carried out to verify their effectiveness.     

Impact analysis of maritime cabotage legislations on liner hub-and-spoke shipping network design

Maritime cabotage is a legislation published by a particular coastal country, which is used to conduct the cargo transportation between its two domestic ports. This paper proposes a two-phase mathematical programming model to formulate the liner hub-and-spoke shipping network design problem subject to the maritime cabotage legislations, i.e., the hub location and feeder allocation problem for phase I and the ship route design with ship fleet deployment problem for phase II. The problem in phase I is formulated as a mixed-integer linear programming model. By developing a hub port expanding technique, the problem in phase II is formulated as a vehicle routing problem with pickup and delivery. A Lagrangian relaxation based solution method is proposed to solve it. Numerical implementations based on the Asia–Europe–Oceania shipping services are carried out to account for the impact analysis of the maritime cabotage legislations on liner hub-and-spoke shipping network design problem.     

Group-shop scheduling with sequence-dependent set-up and transportation times

This paper considers a group-shop scheduling problem (GSSP) with sequence-dependent set-up times (SDSTs) and transportation times. The GSSP provides a general formulation including the job-shop and the open-shop scheduling problems. The consideration of set-up and transportation times is among the most realistic assumptions made in the field of scheduling. In this paper, we study the GSSP with transportation and anticipatory SDSTs, where jobs are released at different times and there are several transporters to carry jobs. The objective is to find a job schedule that minimizes the makespan, that is, the time at which all jobs are completed and transported to the warehouse (or to the customer). The problem is formulated as a disjunctive programming problem and then prepared in a form of mixed integer linear programming (MILP). Due to the non-deterministic polynomial-time hardness (NP-hardness) of the GSSP, large instances cannot be optimally solved in a reasonable amount of time. Therefore, a genetic algorithm (GA) hybridized with an active schedule generator is proposed to tackle large-sized instances. Both Baldwinian and Lamarckian versions of the proposed hybrid algorithm are then implemented and evaluated through computational experiments.     

平行机物流排序的近似算法

本文研究一个两阶段物流排序问题,即第一阶段工件在平行机上加工,在第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.优化的目标是使工件带权送到的时间与运输费用的总和为最小.应用动态规划及组合优化方法,分别研究“满足一致性条件”和一般情形下该问题的多项式时间近似算法,并分析算法的性能比.     

A two-stage stochastic programming framework for transportation planning in disaster response

This study proposes a two-stage stochastic programming model to plan the transportation of vital first-aid commodities to disaster-affected areas during emergency response. A multi-commodity, multi-modal network flow formulation is developed to describe the flow of material over an urban transportation network. Since it is difficult to predict the timing and magnitude of any disaster and its impact on the urban system, resource mobilization is treated in a random manner, and the resource requirements are represented as random variables. Furthermore, uncertainty arising from the vulnerability of the transportation system leads to random arc capacities and supply amounts. Randomness is represented by a finite sample of scenarios for capacity, supply and demand triplet. The two stages are defined with respect to information asymmetry, which discloses uncertainty during the progress of the response. The approach is validated by quantifying the expected value of perfect and stochastic information in problem instances generated out of actual data.     

Dynamic programming based metaheuristics for the dial-a-ride problem

The organization of a specialized transportation system to perform transports for elderly and handicapped people is usually modeled as dial-a-ride problem. Users place transportation requests with specified pickup and delivery locations and times. The requests have to be completed under user inconvenience considerations by a specified fleet of vehicles. In the dial-a-ride problem, the aim is to minimize the total travel times respecting the given time windows, the maximum user ride times, and the vehicle restrictions. This paper introduces a dynamic programming algorithm for the dial-a-ride problem and demonstrates its effective application in (hybrid) metaheuristic approaches. Compared to most of the works presented in literature, this approach does not make use of any (commercial) solver. We present an exact dynamic programming algorithm and a dynamic programming based metaheuristic, which restricts the considered solution space. Then, we propose a hybrid metaheuristic algorithm which integrates the dynamic programming based algorithms into a large neighborhood framework. The algorithms are tested on a given set of benchmark instances from the literature and compared to a state-of-the-art hybrid large neighborhood search approach.     

A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

Emergency Logistics Planning in Natural Disasters

Logistics planning in emergency situations involves dispatching commodities (e.g., medical materials and personnel, specialised rescue equipment and rescue teams, food, etc.) to distribution centres in affected areas as soon as possible so that relief operations are accelerated. In this study, a planning model that is to be integrated into a natural disaster logistics Decision Support System is developed. The model addresses the dynamic time-dependent transportation problem that needs to be solved repetitively at given time intervals during ongoing aid delivery. The model regenerates plans incorporating new requests for aid materials, new supplies and transportation means that become available during the current planning time horizon. The plan indicates the optimal mixed pick up and delivery schedules for vehicles within the considered planning time horizon as well as the optimal quantities and types of loads picked up and delivered on these routes. In emergency logistics context, supply is available in limited quantities at the current time period and on specified future dates. Commodity demand is known with certainty at the current date, but can be forecasted for future dates. Unlike commercial environments, vehicles do not have to return to depots, because the next time the plan is re-generated, a node receiving commodities may become a depot or a former depot may have no supplies at all. As a result, there are no closed loop tours, and vehicles wait at their last stop until they receive the next order from the logistics coordination centre. Hence, dispatch orders for vehicles consist of sets of “broken” routes that are generated in response to time-dependent supply/demand. The mathematical model describes a setting that is considerably different than the conventional vehicle routing problem. In fact, the problem is a hybrid that integrates the multi-commodity network flow problem and the vehicle routing problem. In this setting, vehicles are also treated as commodities. The model is readily decomposed into two multi-commodity network flow problems, the first one being linear (for conventional commodities) and the second integer (for vehicle flows). In the solution approach, these sub-models are coupled with relaxed arc capacity constraints using Lagrangean relaxation. The convergence of the proposed algorithm is tested on small test instances as well as on an earthquake scenario of realistic size.     

A stochastic bi-objective location model for strategic reverse logistics

In this paper we propose a comprehensive model for reverse logistics planning where many real-world features are considered such as the existence of several facility echelons, multiple commodities, choice of technology and stochasticity associated with transportation costs and waste generation. Moreover, we adopt a bi-objective model for the problem. First, the cost for building and operating the network is to be minimized. Second, the obnoxious effect caused by the reverse network facilities is also to be minimized. A two-stage stochastic bi-objective mixed-integer programming formulation is proposed, in which the strategic decisions are considered in the first stage and the tactical/operational decisions in the second one. A set of different scenarios is considered, and the extensive form of the deterministic equivalent problem is presented. This model is tested with a case study based on some data from the Spanish province of Cordoba. Nondominated solutions are obtained by combining the two different objectives and by using a general solver.     

A hybrid heuristic approach for the multi-commodity one-to-one pickup-and-delivery traveling salesman problem

This paper addresses an extension of the Traveling Salesman Problem where a vehicle with a limited capacity must transport commodities. Each commodity has a weight, and exactly one origin and one destination. The objective is to find a minimum length Hamiltonian tour satisfying all the transportation requests without ever violating the capacity constraint. We propose for this problem a hybrid heuristic approach that combines the GRASP and VND metaheuristic techniques. Two variants of the method are presented, one of them using a mathematical programming based local search. We conduct computational experiments to compare the developed algorithms. The experiments show that they improve the best known solutions for a set of instances from the literature, and are able to cope with instances with up to 300 customers and 600 commodities in a reasonable amount of computation time.     

Integrated scheduling of crane handling and truck transportation in a maritime container terminal

This paper studies the interactions between crane handling and truck transportation in a maritime container terminal by addressing them simultaneously. Yard trucks are shared among different ships, which helps to reduce empty truck trips in the terminal area. The problem is formulated as a constraint programming model and a three-stage algorithm is developed. At the first stage, crane schedules are generated by a heuristic method. At the second stage, the multiple-truck routing problem is solved based on the precedence relations of the transportation tasks derived from the first stage. At the last stage a complete solution is constructed by using a disjunctive graph. The three procedures are linked by an iterative structure, which facilitates the search for a good solution. The computational results indicate that the three-stage algorithm is effective for finding high-quality solutions and can efficiently solve large problems.     

基于不确定理论的原油海运网络连通可靠性研究

原油海运网络是原油进口国的海上生命线,为科学衡量网络中节点受到突发事件影响后的原油海运网络的连通可靠性,本文采用不确定变量来描述突发事件发生后各节点的连通性,引入不确定理论对原油海运网络连通可靠性进行评估,并建立了不确定原油海运网络的最可靠路径选择模型。本文不确定变量的引入不再依赖较多的历史数据去描绘节点失效的概率分布,而且提出的最可靠路径选择模型可以确保突发事件发生后原油的及时运输。本文还提出了α-最可靠路径和最大测度最可靠路径选择问题,给出不确定原油海运网络最可靠路径风险值的不确定分布,为突发事件发生后决策者的路径选择提供依据。本文以中国进口原油海运网络为例作案例分析。     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

Freight transportation in railway networks with automated terminals: A mathematical model and MIP heuristic approaches

In this paper we propose a planning procedure for serving freight transportation requests in a railway network with fast transfer equipment at terminals. We consider a transportation system where different customers make their requests (orders) for moving boxes, i.e., either containers or swap bodies, between different origins and destinations, with specific requirements on delivery times. The decisions to be taken concern the route (and the corresponding sequence of trains) that each box follows in the network and the assignment of boxes to train wagons, taking into account that boxes can change more than one train and that train timetables are fixed.The planning procedure includes a pre-analysis step to determine all the possible sequences of trains for serving each order, followed by the solution of a 0-1 linear programming problem to find the optimal assignment of each box to a train sequence and to a specific wagon for each train in the sequence. This latter is a generalized assignment problem which is NP-hard. Hence, in order to find good solutions in acceptable computation times, two MIP heuristic approaches are proposed and tested through an experimental analysis considering realistic problem instances.     

Optimal fleet composition and periodic routing of offshore supply vessels

The supply vessel planning problem is a maritime transportation problem faced by amongst others the energy company Statoil. A set of offshore installations requires supplies from an onshore supply depot on a regular basis, a service performed by a fleet of offshore supply vessels. The problem consists of determining the optimal fleet composition of offshore supply vessels and their corresponding weekly voyages and schedules. We present a voyage-based solution method for the supply vessel planning problem. A computational study shows how the solution method can be used to solve real-life problems. Statoil has implemented a planning tool based on the voyage-based solution method and reports significant savings.     

Scheduling flexible job-shops with transportation times: Mathematical models and a hybrid imperialist competitive algorithm

After the completion of a job on a machine, it needs to be transported to the next machine, actually taking some time. However, the transportation times are commonly neglected in the literature. This paper incorporates the transportation times between the machines into the flexible job-shop scheduling problem. We mathematically formulate the problem by two mixed integer linear programming models. Since the problem is NP-hard, we propose an adaptation of the imperialist competitive algorithm hybridized by a simulated annealing-based local search to solve the problem. Various operators and parameters of the algorithm are calibrated using the Taguchi method. The presented algorithm is assessed by comparing it against two other competitive algorithms in the literature. The computational results show that this algorithm has an outstanding performance in solving the problem.     

Modelling and solving an <Emphasis Type="Italic">m</Emphasis>-location, <Emphasis Type="Italic">n</Emphasis>-courier,priority-based planning problem on a network

In this paper, we study an m-location, n-courier, priority-based planning problem on a network, which we refer to as the Courier Planning Problem (CPP). The CPP arises on a daily basis in the context of planning the transportation of materials and personnel in peacetime for the Turkish Armed Forces. The main issue addressed in CPP is to transport as many of deliverables as possible from their origins to their destinations via a fleet of transportation assets (couriers) that operate at fixed routes and schedules. Priorities must be taken into account and constraints on the routes, operating schedules, and capacities of the transportation assets must be obeyed. Time windows may be specified for some or all transportation requests and must be satisfied. We study the CPP as well as its two extensions, and present integer programming formulations based on the multi-commodity flow structure. The formulations are tested on real world-based data and display satisfactory computational performance. Our main contributions are to develop an effective formulation scheme for a complicated large-scale real world problem and to demonstrate that such problems are solvable via commercial general purpose solvers through meticulous modelling.     

A linear programming priority method for a fuzzy transportation problem with non-linear constraints

Demand and supply pattern for most products varies during their life cycle in the markets. In this paper, the author presents a transportation problem with non-linear constraints in which supply and demand are symmetric trapezoidal fuzzy value. In order to reflect a more realistic pattern, the unit of transportation cost is assumed to be stochastic. Then, the non-linear constraints are linearized by adding auxiliary constraints. Finally, the optimal solution of the problem is found by solving the linear programming problem with fuzzy and crisp constraints and by applying fuzzy programming technique. A new method proposed to solve this problem, and is illustrated through numerical examples. Multi-objective goal programming methodology is applied to solve this problem. The results of this research were developed and used as one of the Decision Support System models in the Logistics Department of Kayson Co.     

A dual ascent approach to the fixed-charge capacitated network design problem

In this paper we consider the problem of constructing a network over which a number of commodities are to be transported. Fixed costs are associated to the construction of network arcs and variable costs are associated to routing of commodities. In addition, one capacity constraint is related to each arc. The problem is to determine a network design that minimizes the total cost; i.e., it balances the construction and operating costs. A dual ascent procedure for finding improved lower bounds and near-optimal solutions for the fixed-charge capacitated network design problem is proposed. The method is shown to generate tighter lower bounds than the linear programming relaxation of the problem.