Integrated planning of loaded and empty container movements

Efficiently planning drayage operations is an important task for transportation companies since these operations constitute a large part of the cost of an intermodal transport. In this paper, a full truckload vehicle routing problem for transporting loaded and empty containers in drayage operations is studied. For empty container transports, either the origin or the destination is not predefined. The problem is formulated as an asymmetric multiple vehicle Travelling Salesman Problem with Time Windows (am-TSPTW). Two solution approaches are proposed: a sequential and an integrated approach. For both approaches, a single- and a two-phase deterministic annealing algorithm are presented. Results show that the proposed algorithms are able to find good quality solutions in a small amount of computation time. The integrated approach clearly outperforms the sequential one and the results confirm the advantage of using a two-phase algorithm for vehicle routing problems with hierarchical objectives. Finally, it is shown that the proposed integrated solution method improves previous results on a similar problem.     

Heuristic-based truck scheduling for inland container transportation

A truck scheduling problem for container transportation in a local area with multiple depots and multiple terminals including containers as a resource for transportation is addressed. Four types of movements of containers as inbound full, outbound full, inbound empty and outbound empty movements as well as the time windows at both the origin and the destination are considered. The total operating time of all trucks in operation is taken as the optimization criterion that has to be minimized. The problem is mathematically modeled based on a preparative graph formulation and falls into an extension of the multiple traveling salesman problem with time windows (m-TSPTW). The window partition based solution method for the m-TSPTW in Wang and Regan (Transp Res Part B: Methodol 36:97–112, 2002) is modified so that its computation time is reduced greatly. The experiments based on a number of randomly generated instances indicate that the modified method is quite fast and the quality of solutions is relatively high for the m-TSPTW. These experiments also demonstrate that our approach is able to generate high-quality results for the equivalent truck scheduling and inland container movement problem in container drayage operations.     

How to park freight trains on rail–rail transshipment yards: the train location problem

In modern rail–rail transshipment yards huge gantry cranes spanning all railway tracks allow for an efficient transshipment of containers between different freight trains. This way, multiple trains loaded with cargo for varying destinations can be consolidated to a reduced number of homogeneous trains, which is an essential requirement of hub-and-spoke railway systems. An important problem during the daily operations of such a transshipment yard is the train location problem, which assigns each train of a given pulse to a railway track (vertical position) and decides on each train’s parking position on the track (horizontal position), so that the distances of container movements are minimized and the overall workload is equally shared among cranes. For this problem a mathematical model is presented; different heuristic solution procedures are described and tested in a comprehensive computational study. The results show that our procedures allow for a remarkable reduction of train processing time compared with typical real-world train location policies.     

Synchronized routing of active and passive means of transport

This paper addresses a routing problem where the fulfillment of transport requests requires two types of transport resources, namely, passive and active means of transport. The passive means are used for holding the cargo that is to be shipped from pickup to delivery locations. The active means take up the passive means and carry them from one location to another. Compared to classical vehicle routing problems, the additional challenge in this combined routing problem is that the operations of both transport resources have to be synchronized. In this paper, we provide a modeling approach for the joint routing of passive and active means of transport. We solve the problem by large neighborhood search meta-heuristics that utilize various problem-specific components, for example local search techniques for the routes of active and passive means. A computational study on a large set of benchmark instances is used for assessing the performance of the meta-heuristics.     

Mathematical models and solution methods for optimal container terminal yard layouts

In this paper, we introduce an integer linear program for planning the layout of container yards. We concentrate on a special layout class of container yards which we call yard layout with transfer lanes. For those layouts typically rubber tired gantry cranes are used for stacking operations and trucks for horizontal transports. We show that the optimization model can be formulated as a special type of a resource constrained shortest path problem for which the LP relaxation always has at least one integer optimal solution. This model is restricted to a rectangular storage yard which allows a linear formulation. For an arbitrary shaped container yard we adopt the model and develop a variable neighborhood descent (VND) heuristic for solving non-rectangular instances. Concerning the rectangular case, we show that the VND heuristic achieves optimal solutions for 38% of the realistic test instances.     

The value of integrating order picking and vehicle routing decisions in a B2C e-commerce environment

In B2C e-commerce sales, customers expect a fast and low-cost delivery. To be able to fulfil these customer expectations, both warehouse and distribution operations have to be performed in an efficient and effective way. Ideally, these two supply chain functions should be considered simultaneously in an integrated problem since they are interrelated. In this paper, a record-to-record travel algorithm is proposed to solve the integrated order picking-vehicle routing problem (I-OP-VRP). Experiments with both small-size and large-size instances are conducted. Furthermore, the integrated approach is compared with an approach in which both problems are solved sequentially. Results show that integration leads to increased service levels, i.e. it allows to shorten the time between placing an order and receiving the goods. On top, the integrated approach leads to costs savings of on average 1.8%. Thus, integration is indispensable for a fast and cost-efficient delivery of goods.     

A priority scheduling approach for flexible job shops with multiple process plans

This paper considers the job shop scheduling problem with alternative operations and machines, called the flexible job shop scheduling problem. As an extension of previous studies, operation and routing flexibilities are considered at the same time in the form of multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. Since the problem is highly complicated, we suggest a practical priority scheduling approach in which the two decisions are done at the same time using a combination of operation/machine selection and job sequencing rules. The performance measures used are minimising makespan, total flow time, mean tardiness, the number of tardy jobs, and the maximum tardiness. To compare the performances of various rule combinations, simulation experiments were done on the data for hybrid systems with an advanced reconfigurable manufacturing system and a conventional legacy system, and the results are reported.     

A heuristic for dynamic yard crane deployment in a container terminal

Rubber Tired Gantry Cranes (RTGCs) are the most widely used pieces of equipment in the Hong Kong sea-freight container yards. Workload distribution in the yard changes continuously over time. The dynamic deployment of RTGCs is an important issue in yard operation management. This paper investigates the dynamic crane deployment problem with the objective of determining the crane deployment frequency and routes over a planning horizon to minimize the total workload overflow. The problem is formulated as a mixed integer programming model. A heuristic algorithm is then developed to solve problems of practical sizes. The heuristic quickly finds a near optimal solution for crane deployment operation.     

Simulation-based optimisation approach for the stochastic two-echelon logistics problem

This work proposes a simulation-based optimisation approach for the two-echelon vehicle routing problem with stochastic demands (2E-VRPSD). In the proposed 2E-VRPSD, freight delivery from the depot to the customers is managed by shipping the freight through intermediate satellites, while each customer has a stochastic demand. The 2E-VRPSD is an extension of the famous capacitated vehicle routing problem with stochastic demands and the two-echelon vehicle routing problem (2E-VRP). A tabu search algorithm is designed to solve the 2E-VRPSD, in which Monte Carlo sampling is adopted to tackle the issue of stochastic demands. Modified two-echelon vehicle routing problem benchmark instances are used in the numerical experiments. The computational results show the advantage of the proposed simulation-based approach.     

A computerized approach to the New York Cityschool bus routing problem

Transportation is an area where operations research has had a great impact on systems by improving service quality and reducing operating costs. In particular, one of the most visible applications is in routing and scheduling school buses. In this paper we investigate various issues related to the development of a computerized system to help route and schedule school buses throughout the five boroughs of New York City. The routing problem presents many challenges because of its magnitude, the vast resources involved and the intricacies one encounters when routing in a completely urban environment. We analyze various aspects of the problem including the generation of routes in the Borough of Manhattan and provide a solution requiring far fewer buses than are currently in use. The computerized system, called CATS, incorporating many of the results obtained in this research, is currently being used to route Special Education students.     

<Emphasis Type="Italic">k</Emphasis>-Shortest routing of trains on shunting yards

We consider the problem of designing algorithmic support for k-best routing decisions in train shunting scheduling. A study at the Netherlands Railways revealed that planners like to interact with the solution process of finding suitable routes. Two types of interaction were required: the possibility of assigning specific tracks to a route and of preventing the assignment of specific tracks to a route. The paper develops insights in the structure of the cost matrix in this k-best optimization problem. These dominance results are used in a two stage k-shortest path algorithm to support this task of the shunting planners. The solution approach determines the optimal sequence of the tracks that manually have been added to the route and determines the k shortest paths in this network. The approach is implemented in a prototype of a support system for shunting planners. The required calculation times for practical instances of the problem with varying numbers of alternative solutions (k ≤ 8) and intermediate tracks (m ≤ 5) are between 0.1 and 1.4 s. These calculation times are acceptable to provide adequate support to the planners of these shunting yards. Supported by the Netherlands Railways, Project “Rintel 4a”. We gratefully acknowledge the management and planners of this company. Specifically, we would like to thank Dr. L.G. Kroon and the planners of location Zwolle for their willingness to co-operate.     

Linguistic-based meta-heuristic optimization model for flexible job shop scheduling

In this paper, a linguistic based meta-heuristic modelling and solution approach for solving the Flexible Job Shop Scheduling Problem (FJSSP) is presented. FJSSP is an extension of the classical job-shop scheduling problem. The present problem definition is to assign each operation to a machine out of a set of capable machines ( the routing problem ) and to order the operations on the machines ( the sequencing problem ), such that a predefined performance measure is optimized. The scope of the problem is widened by taking into account the alternative process plans for each part ( process plan selection problem ) in the present study. Moreover, instead of using operations to represent product processing requirements and machine processing capabilities, machine independent capability units, which are known as Resource Elements (RE), are used. Representation of unique and shared capability boundaries of machine tools and part processing requirements is possible via RE. Using REs in scheduling can also reduce the problem size. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls. Using these controls and the Giffler and Thompson (1960) priority rule-based heuristic, a simulated annealing algorithm is developed to solve FJSSP. This novel approach simplifies the modelling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its solution. The results obtained from the computational study have shown that the proposed algorithm can solve this complex problem effectively within reasonable time. The results have also given some insights on the effect of the selection of dispatching rules and the flexibility level on the job shop performance. It is observed that the effect of dispatching rule selection on the job shop performance diminishes by increasing the job shop flexibility.     

A genetic algorithm for manufacturing cell formation with multiple routes and multiple objectives

This paper presents a genetic algorithm (GA) approach to the machine-component grouping problem with multiple objectives: minimizing costs due to intercell and intracell part movements; minimizing the total within cell load variation; and minimizing exceptional elements. Manufacturing cells are formed based on production data, e.g. part routing sequence, production volume and workload. Also, we will discuss the implication of part alternative routings and the method we suggest to deal with it. Special genetic operators are developed and multiple experiments are performed. Finally, the results obtained with the proposed algorithm on the tested problems are compared with those of others.     

A hybrid genetic algorithm for the multi-depot open vehicle routing problem

This paper studies the multi-depot open vehicle routing problem (MDOVRP), a variant of the vehicle routing problem (VRP), in which vehicles start from several depots and are not required to return to the depot. Despite the vast amount of literature about VRPs, the MDOVRP has received very little attention from researchers. In this paper, a new hybrid genetic algorithm is presented for finding the routes that minimize the traveling cost of the vehicles. Computational results on a number of test instances indicate the proposed algorithm dominates the CPLEX solver and the existing approach in the literature. Meanwhile, experiments are conducted on multi-depot VRP benchmarks, and the results are compared with a sophisticated tabu search approach and an exact method.     

Scheduling the operations of a double-load crane in slab yards

This paper studies a double-load crane scheduling problem (DLCSP) in steel slab yards. A slab yard stores slabs in stacks. To prepare for use in production, some slabs need to be moved from one place to another. These movement tasks are performed by a double-load crane which can hold up to two slabs simultaneously. Given a set of tasks and possibly precedence relationships among them, the scheduling problem is to allocate the tasks to double-load operations and determine the schedule for the crane to perform the tasks so as to minimise the makespan. The problem is first formulated as a mixed integer linear programming (MILP) model with variables representing the order of tasks. Based on properties of the problem, it is then reformulated from a crane operation perspective. Computational experiments are carried out on practical data collected from a steel company. The results show that both models can solve practical sized problems optimally, with the second model being more efficient.     

Q-Learning Based Routing Protocol for Congestion Avoidance

The end-to-end delay in a wired network is strongly dependent on congestion on intermediate nodes. Among lots of feasible approaches to avoid congestion efficiently, congestion-aware routing protocols tend to search for an uncongested path toward the destination through rule-based approaches in reactive/incident-driven and distributed methods. However, these previous approaches have a problem accommodating the changing network environments in autonomous and self-adaptive operations dynamically. To overcome this drawback, we present a new congestion-aware routing protocol based on a Q-learning algorithm in software-defined networks where logically centralized network operation enables intelligent control and management of network resources. In a proposed routing protocol, either one of uncongested neighboring nodes are randomly selected as next hop to distribute traffic load to multiple paths or Q-learning algorithm is applied to decide the next hop by modeling the state, Q-value, and reward function to set the desired path toward the destination. A new reward function that consists of a buffer occupancy, link reliability and hop count is considered. Moreover, look ahead algorithm is employed to update the Q-value with values within two hops simultaneously. This approach leads to a decision of the optimal next hop by taking congestion status in two hops into account, accordingly. Finally, the simulation results presented approximately 20% higher packet delivery ratio and 15% shorter end-to-end delay, compared to those with the existing scheme by avoiding congestion adaptively.     

Hierarchical multiobjective routing model in Multiprotocol Label Switching networks with two service classes – a Pareto archive strategy

The article begins by reviewing a two-level hierarchical multicriteria routing model for Multiprotocol Label Switching networks with two service classes (QoS, i.e. with Quality of Service requirements, and Best Effort services) and alternative routing, as well as the foundations of a heuristic resolution approach, previously proposed by the authors. Afterwards a new variant of this heuristic approach, which includes a Pareto archive strategy, is described. In this archive, non-dominated solutions obtained throughout the heuristic are kept. At the end of the main procedure of the heuristic, these solutions are evaluated and a final solution for the routing problem is chosen using a reference point-based approach. The application of this procedure to two test networks will show, with analytic and discrete-event simulation models, that, in certain initial conditions, this approach provides improvements in the final results concerning the top-level objective functions, especially in more ‘difficult’ situations detected through sensitivity analysis.     

ECO-BAT: A New Routing Protocol for Energy Consumption Optimization Based on BAT Algorithm in WSN

Wireless sensor network (WSN) has been widely used due to its vast range of applications. The energy problem is one of the important problems influencing the complete application. Sensor nodes use very small batteries as a power source and replacing them is not an easy task. With this restriction, the sensor nodes must conserve their energy and extend the network lifetime as long as possible. Also, these limits motivate much of the research to suggest solutions in all layers of the protocol stack to save energy. So, energy management efficiency becomes a key requirement in WSN design. The efficiency of these networks is highly dependent on routing protocols directly affecting the network lifetime. Clustering is one of the most popular techniques preferred in routing operations. In this work we propose a novel energy-efficient protocol for WSN based on a bat algorithm called ECO-BAT (Energy Consumption Optimization with BAT algorithm for WSN) to prolong the network lifetime. We use an objective function that generates an optimal number of sensor clusters with cluster heads (CH) to minimize energy consumption. The performance of the proposed approach is compared with Low-Energy Adaptive Clustering Hierarchy (LEACH) and Energy Efficient cluster formation in wireless sensor networks based on the Multi-Objective Bat algorithm (EEMOB) protocols. The results obtained are interesting in terms of energy-saving and prolongation of the network lifetime.     

Production planning for flexible flow systems with limited machine flexibility

A flexible manufacturing system (FMS) is highly capital-intensive and FMS users are concerned with achieving high system utilization. The production planning function for setting up an FMS prior to production should be developed in order to make the most of the potential benefits of FMSs. We consider two production planning problems of grouping and loading a flexible flow system, which is an important subset of FMSs where the routing of parts is unidirectional. We show that considering this routing restriction as well as limited machine flexibility strongly affects both the solution techniques and the quality of the solutions. Because of the complexity of the problem, we present a heuristic approach that decomposes the original problem into three interrelated subproblems. We show that the proposed approach usually finds a near-optimum solution and is superior to an approach that exists in the literature of FMS production planning. We also introduce effective heuristic methods for two new subproblems that arise because of the unidirectional flow precedence and flexibility constraints. Computational results are reported and future research issues are discussed.     

Control of Material Handling Transporter in Automated Manufacturing

This paper presents a real time routing method for material handling transporters in automated manufacturing shops where the performance criterion is to maximize throughput The static version of the routing problem is identified as a one machine due date problem with sequence dependent processing times and sequence dependent due dates. For real time application, a heuristic method is proposed, and its performance is evaluated and compared to other currently known rules using discrete simulation on hypothetical cell operations.