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.     

A Genetic Algorithm with a Compact Solution Encoding for the Container Ship Stowage Problem

The purpose of this study is to develop an efficient heuristic for solving the stowage problem. Containers on board a container ship are stacked one on top of the other in columns, and can only be unloaded from the top of the column. A key objective of stowage planning is to minimize the number of container movements. A genetic algorithm technique is used for solving the problem. A compact and efficient encoding of solutions is developed, which reduces significantly the search space. The efficiency of the suggested encoding is demonstrated through an extensive set of simulation runs and its flexibility is demonstrated by successful incorporation of ship stability constraints.     

A heuristic for the circle packing problem with a variety of containers

In this paper we present a heuristic algorithm based on the formulation space search method to solve the circle packing problem. The circle packing problem is the problem of finding the maximum radius of a specified number of identical circles that can be fitted, without overlaps, into a two-dimensional container of fixed size. In this paper we consider a variety of containers: the unit circle, unit square, rectangle, isosceles right-angled triangle and semicircle. The problem is formulated as a nonlinear optimization problem involving both Cartesian and polar coordinate systems.Formulation space search consists of switching between different formulations of the same problem, each formulation potentially having different properties in terms of nonlinear optimization. As a component of our heuristic we solve a nonlinear optimization problem using the solver SNOPT.Our heuristic improves on previous results based on formulation space search presented in the literature. For a number of the containers we improve on the best result previously known. Our heuristic is also a computationally effective approach (when balancing quality of result obtained against computation time required) when compared with other work presented in the literature.     

An adaptive guidance meta-heuristic for the vehicle routing problem with splits and clustered backhauls

This paper presents the case study of an Italian carrier, Grendi Trasporti Marittimi, which provides freight transportation services by trucks and containers. Its trucks deliver container loads from a port to import customers and collect container loads from export customers to the same port. In this case study, all import customers in a route must be serviced before all export customers, each customer can be visited more than once and containers are never unloaded or reloaded from the truck chassis along any route. We model the problem using an Integer Linear Programming formulation and propose an Adaptive Guidance metaheuristic. Our extensive computational experiments show that the adaptive guidance algorithm is capable of determining good-quality solutions in many instances of practical or potential interest for the carrier within 10?min of computing time, whereas the mathematical formulation often fails to provide the first feasible solution within 3?h of computing time.     

Transportation problem with nonlinear side constraints a branch and bound approach

In a container terminal management, we are often confronted with the following problem: how to assign a reasonable depositing position for an arriving container, so that the efficiency of searching for and loading of a container later can be increased. In this paper, the problem is modeled as a transportation problem with nonlinear side constraints (TPNSC). The reason of nonlinear side constraints arising is that some kinds of containers cannot be stacked in the same row (the space of storage yard is properly divided into several rows). A branch and bound algorithm is designed to solve this problem. The algorithm is based on the idea of using disjunctive arcs (branches) for resolving conflicts that are created whenever some conflicting kinds of containers are deposited in the same row. During the branch and bound, the candidate problems are transformed into classical transportation problems, so that the efficient transportation algorithm can be applied, at the same time the reoptimization technique is employed during the branch and bound. Further, we design a heuristic to obtain a feasible initial solution for TPNSC in order to prune some candidates as early and/or as much as possible. We report computational results on randomly generated problems.     

Multiple Container Packing: A Case Study of Pipe Packing

While the problem of packing single containers and pallets has been thoroughly investigated very little attention has been given to the efficient packing of multiple container loads. Normally in practice a multiple container load is packed by a single container algorithm used in a greedy fashion. This paper introduces the issues involved in multiple container loading. It lays out three different strategies for solving the problem: sequential packing using a single container heuristic, pre-allocating items to the containers and choosing container loads using simultaneous packing models. The principal simultaneous models are pattern selection IP models. We present an application of packing pipes in shipping containers using two pattern selection IP models, a pattern selection heuristic, a sequential greedy algorithm and a pre-allocation method. The experimental results use randomly generated data sets. We discuss several useful insights into the methods and show that for this application the pattern selection methods perform best.     

Combined Sea and Land Transportation

An important problem today in the field of transportation is the standardization of the cargo, e.g. by using containers, and the design of the handling and transportation equipment for the specific cargo to be transported.The paper presents a method for determining the transportation system with emphasis on sea transport. Thus the cargo is to be transported by sea from the factory to customers spread over a large region, e.g. Europe. The problem is to select the ports of call, the quantities to be delivered at the ports, as well as the size and type of vessel.This problem resembles the warehouse location problem (the location of ports) but requires in addition the determination of ship size, type of ship and whether one or more ports should be called at on each journey with a single ship. A discussion is also presented as to the possibility of considering randomness in the system with respect to customer demand and weather conditions.The method used resembles that suggested by Baumol and Wolfe for the ware-house location problem. A concave function of the quantities delivered at each port is derived and this is then shown to converge to a local optimum.An example is solved to illustrate the method.     

Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type

This paper presents exact and heuristic solution procedures for a multiproduct capacitated facility location (MPCFL) problem in which the demand for a number of different product families must be supplied from a set of facility sites, and each site offers a choice of facility types exhibiting different capacities. MPCFL generalizes both the uncapacitated (or simple) facility location (UFL) problem and the pure-integer capacitated facility location problem. We define a branch-and-bound algorithm for MPCFL that utilizes bounds formed by a Lagrangian relaxation of MPCFL which decomposes the problem into UFL subproblems and easily solvable 0-1 knapsack subproblems. The UFL subproblems are solved by the dual-based procedure of Erlenkotter. We also present a subgradient optimization-Lagrangian relaxation-based heuristic for MPCFL. Computational experience with the algorithm and heuristic are reported. The MPCFL heuristic is seen to be extremely effective, generating solutions to the test problems that are on average within 2% of optimality, and the branch-and-bound algorithm is successful in solving all of the test problems to optimality.     

Alternative algorithms for the optimization of a simulation model of a multimodal container terminal

Multimodal container terminals (MMCTs) are very complex and consequently require synchronization and balancing of container transfers at each node. The problem being investigated is the minimization of ship delays at the port by considering handling and travelling time of containers from the time the ship arrives at port until all the containers from that ship leave the port. When dealing with export containers, the problem would be that of the handling and travelling time of the containers from when they first arrive at the port until the ship carrying the containers departs from the port. Owing to the dynamic nature of the environment, a large number of timely decisions have been reviewed in accordance with the changing conditions of the MMCTs. The model has been run and tested with a small-size problem using CPLEX. A more realistic model is extremely difficult to solve and is in fact proven to be computationally intractable (NP-hard). Metaheuristics have been developed to deal with the intractability so that near-optimal solutions could be obtained in reasonable time.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

Plant location and procurement planning in knockdown production systems

We consider an integrated problem of plant location and capacity planning for components procurement in knockdown production systems. The problem is that of determining the schedule of opening components manufacturing plants, plans for acquisition of capacities in opened components manufacturing plants, and plans for components procurement in final assembly plants with the objective of minimizing the sum of fixed costs for opening plants, acquisition and operation costs of facilities, and delivery and subcontracting costs of components. The problem is formulated as a mixed integer linear program and solved by a two-stage solution procedure. In the solution procedure, the problem is decomposed into two tractable subproblems and these subproblems are solved sequentially. In the first stage, a dynamic plant location problem is solved using a cut and branch algorithm based on Gomory cuts, while a multiperiod capacity planning problem is solved in the second stage by a heuristic algorithm that uses a cut and branch algorithm and a variable reduction scheme. The solution procedure is tested on problems of a practical size and results show that the procedure gives reasonably good solutions.     

考虑路径冲突的AGV配置与调度优化

合理调度有限的码头资源以满足船舶的装卸时间要求是自动化集装箱码头的重要目标之一。针对自动化集装箱码头自动导引车(automated guided vehicle,AGV)配置与调度问题,考虑船舶装卸时间要求和AGV运输过程中的路径冲突,提出分阶段调度策略。将船舶装卸作业分为卸船阶段、装卸同步阶段、装船阶段三个阶段,在每个阶段中,建立以最小化最大完工时间和最小化AGV空载和等待时间为双目标的调度优化模型,并设计基于NSGA-Ⅱ的启发式算法求解。根据本阶段的实际完工时间,从最优解集中选择下一阶段AGV的配置与调度方案。最后对比其他调度方案表明本文调度方案能够满足集装箱船的装卸时间要求,且提高了AGV的利用率,更符合码头实际作业要求。     

Capacity allocation problem with random demands for the rail container carrier

In this paper, we consider the formulation and heuristic algorithm for the capacity allocation problem with random demands in the rail container transportation. The problem is formulated as the stochastic integer programming model taking into account matches in supply and demand of rail container transportation. A heuristic algorithm for the stochastic integer programming model is proposed. The solution to the model is found by maximizing the expected total profit over the possible control decisions under the uncertainty of demands. Finally, we give numerical experiments to demonstrate the efficiency of the heuristic algorithm.     

A Lagrangian relaxation approach to large-scale flow interception problems

The paper presents a tight Lagrangian bound and an efficient dual heuristic for the flow interception problem. The proposed Lagrangian relaxation decomposes the problem into two subproblems that are easy to solve. Information from one of the subproblems is used within a dual heuristic to construct feasible solutions and is used to generate valid cuts that strengthen the relaxation. Both the heuristic and the relaxation are integrated into a cutting plane method where the Lagrangian bound is calculated using a subgradient algorithm. In the course of the algorithm, a valid cut is added and integrated efficiently in the second subproblem and is updated whenever the heuristic solution improves. The algorithm is tested on randomly generated test problems with up to 500 vertices, 12,483 paths, and 43 facilities. The algorithm finds a proven optimal solution in more than 75% of the cases, while the feasible solution is on average within 0.06% from the upper bound.     

Yard template planning in transshipment hubs under uncertain berthing time and position

This paper is concerned with yard management in transshipment hubs, where a consignment strategy is often used to reduce reshuffling and vessel turnaround time. This strategy groups unloaded containers according to their destination vessels. In this strategy, yard template determines the assignment of the spaces (sub-blocks) in the yard to the vessels. This paper studies how to make a good yard template under uncertain environment, for example, uncertain berthing time and berthing positions of the arriving vessels. To reduce the potential traffic congestion of prime movers, the workload distribution of sub-blocks within the yard is considered. A mixed integer programming model is formulated to minimize the expected value of the route length of container transshipping flows in the yard. Moreover, a heuristic algorithm is developed for solving the problem in large-scale realistic environments. Numerical experiments are conducted to validate the efficiency of the proposed algorithm.     

Container stowage planning: a methodology for generating computerised solutions

The container stowage problem concerns the suitable placement of containers in a container-ship on a multi-port journey; it requires consideration of the consequences each placement has on decisions at subsequent ports. A methodology for the automatic generation of computerised solutions to the container stowage problem is shown; objective functions that provide a basis for evaluating solutions are given in addition to the underlying structures and relationships that embody this problem. The methodology progressively refines the placement of containers within the cargo-space of a container ship until each container is specifically allocated to a stowage location. The methodology embodies a two stage process to computerised planning, that of a generalised placement strategy and a specialised placement procedure. Heuristic rules are built into objective functions for each stage that enable the combinatorial tree to be explored in an intelligent way, resulting in good, if not optimal, solutions for the problem in a reasonable processing time.     

An integral LP relaxation for a drayage problem

This paper investigates a drayage problem, where a fleet of trucks must ship container loads from a port to importers and from exporters to the same port, without separating trucks and containers during customer service. We present three formulations for this problem that are valid when each truck carries one container. For the third formulation, we also assume that the arc costs are equal for all trucks, and then we prove that its continuous relaxation admits integer optimal solutions by checking that its constraint matrix is totally unimodular. Under the same hypothesis on costs, even the continuous relaxations of the first two models are proved to admit an integer optimal solution. Finally, the third model is transformed into a circulation problem, that can be solved by efficient network algorithms.     

DCA for solving the scheduling of lifting vehicle in an automated port container terminal

The container was introduced as a universal carrier for various goods in the 1960s and soon became a standard worldwide transportation. The competitiveness of a container seaport is marked by different success factors, particularly the time in port for ships. Operational problems of container terminals is divided into several problems, such as assignment of vessels, loading/unloading and storage of the containers, quay cranes scheduling cite, planning yard cranes cite and assignment of storage containers cite. In this work, the study will focus on piloting yard trucks. Two different types of vehicles can be used, namely automated guided vehicles (AGVs) and lifting vehicles (LVs). An AGV receives a container from a quay crane and transports containers over fixed path. LVs are capable of lifting a container from the ground by itself. The model that we consider is formulated as a mixed integer programming problem, and the difficulty arises when the number of binary variables increases. There are a lot of algorithms designed for mixed integer programming problem such as Branch and Bound method, cutting plane algorithm, . . . By using an exact penalty technique we treat this problem as a DC program in the context of continuous optimization. Further, we combine the DCA with the classical Branch and Bound method for finding global solutions.     

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.     

An arc-exchange decomposition method for multistage dynamic networks with random arc capacities

Multistage dynamic networks with random arc capacities (MDNRAC) have been successfully used for modeling various resource allocation problems in the transportation area. However, solving these problems is generally computationally intensive, and there is still a need to develop more efficient solution approaches. In this paper, we propose a new heuristic approach that solves the MDNRAC problem by decomposing the network at each stage into a series of subproblems with tree structures. Each subproblem can be solved efficiently. The main advantage is that this approach provides an efficient computational device to handle the large-scale problem instances with fairly good solution quality. We show that the objective value obtained from this decomposition approach is an upper bound for that of the MDNRAC problem. Numerical results demonstrate that our proposed approach works very well.