A heuristic algorithm for yard truck scheduling and storage allocation problems

The yard truck scheduling and the storage allocation are two important decision problems affecting the efficiency of container terminal operations. This paper proposes a novel approach that integrates these two problems into a whole. The objective is to minimize the weighted sum of total delay of requests and the total travel time of yard trucks. Due to the intractability of the proposed problem, a hybrid insertion algorithm is designed for effective problem solutions. Computational experiments are conducted to examine the key factors of the problem and the performance of the proposed heuristic algorithm.     

Accounting for population exposure to vehicle-generated pollutants and environmental equity in the toll design problem

The emissions generated by motor vehicles remain a major source of air pollutants that affect public health and contribute to anthropogenic climate change. These negative externalities can be reduced, in part, with the implementation of environmentally oriented road pricing schemes, which can be designed using optimization-based approaches. In this paper, a toll design problem is proposed for determining toll locations and levels that minimize the expected human exposure to air pollutants and the related environmental inequalities, subject to constraints on pollutant concentration levels and implementation costs. The practical use of the proposed problem is hindered in most real-world applications by the computational costs associated with the evaluation of candidate solutions, as is common for network design problems. Furthermore, the problem cannot be expressed analytically given the multiple types of models (e.g., traffic assignment, emissions, air dispersion models) that would be required to evaluate a single design alternative. For these reasons, a derivative-free surrogate-based solution algorithm is proposed for mixed integer problems like the ones considered here. Numerical examples are used to illustrate possible applications of the proposed model and to test the performance of the surrogate-based algorithm. Relative to a joint simulated annealing-genetic algorithm heuristic and a genetic algorithm-based approach, the proposed algorithm found better solutions in fewer function evaluations.     

A reactive tabu search algorithm for the multi-depot container truck transportation problem

A container truck transportation problem that involves multiple depots with time windows at both origins and destinations, including the reposition of empty containers, is formulated as a multi-traveling salesman problem with time windows (m-TSPTW) with multiple depots. Since the problem is NP-hard, a cluster method and a reactive tabu search (RTS) algorithm are developed to solve the problem. The two methods are compared with the mixed integer program which can be used to find optimum solutions for small size problems. The computational results show that the developed methods, particularly the RTS algorithm, can be efficiently used to solve the problem.     

Branch-and-price algorithm for the location-routing problem with time windows

This study proposes a branch-and-price algorithm to solve the Location-Routing Problem with Time Windows (LRPTW) which has never been attempted with the exact solutions before. The problem is solved by the simplex algorithm in the master problem and elementary shortest path problems with resource constraint corresponding to column generation in the subproblem until only the non-negative reduced cost columns remain. The proposed algorithm can solve many testing instances effectively. The computational results and the effect of time windows are also compared and discussed.     

Optimizing a bi-objective inventory model of a three-echelon supply chain using a tuned hybrid bat algorithm

This paper presents a bi-objective VMI problem in a single manufacturer-single vendor multi-retailer (SM-SV-MR) supply chain, which a redundancy allocation problem is incorporated. In the hybridized problem, a manufacturer produces a single item using several machines that work in series, and stores it in a warehouse to replenish one vendor who delivers it to several retailers using the shortest possible route. A novel meta-heuristic, called hybrid bat algorithm (HBA), with calibrated parameters is utilized to find a near-optimum solution. To show the efficiency of HBA, the results are compared to the ones using the traditional BA and a genetic algorithm.     

Hierarchical multi-objective evacuation routing in stadium using ant colony optimization approach

Evacuation planning is a fundamental requirement to ensure that most people can be evacuated to a safe area when a natural accident or an intentional act happens in a stadium environment. The central challenge in evacuation planning is to determine the optimum evacuation routing to safe areas. We describe the evacuation network within a stadium as a hierarchical directed network. We propose a multi-objective optimization approach to solve the evacuation routing problem on the basis of this hierarchical directed network. This problem involves three objectives that need to be achieved simultaneously, such as minimization of total evacuation time, minimization of total evacuation distance and minimal cumulative congestion degrees in an evacuation process. To solve this problem, we designed a modified ant colony optimization (ACO) algorithm, implemented it in the MATLAB software environment, and tested it using a stadium at the Wuhan Sports Center in China. We demonstrate that the algorithm can solve the problem, and has a better evacuation performance in terms of organizing evacuees’ space-time paths than the ACO algorithm, the kth shortest path algorithm and the second generation of non-dominated sorting genetic algorithm were used to improve the results from the kth shortest path algorithm.     

The optimization model for the location of maritime emergency supplies reserve bases and the configuration of salvage vessels

This paper studies the location–allocation–configuration problem of emergency resources in a maritime emergency system and it proposes a discrete nonlinear integer-programming model, which integrates the location, allocation and the configuration problem. The model is converted into a two-stage model keeping the calculation logic. It designs a hybrid heuristic algorithm and a genetic algorithm. The test results show that the hybrid heuristic algorithm is more efficient than the genetic algorithm, the sensitivity analysis studies the influence of some parameters to the final solution and the Uncertainty–Sensitivity justification tool is used to evaluate the assumptions.     

A robust optimization approach to the integrated berth allocation and quay crane assignment problem

This paper investigates the integrated berth allocation and quay crane assignment problem in container terminals. A deterministic model is formulated by considering the setup time of quay cranes. However, data uncertainties widely exist, and it may cause the deterministic solution to be infeasible. To handle the uncertainties, a robust optimization model is established. Furthermore, to control the level of conservativeness, another robust optimization model with the price constraints is proposed. A genetic algorithm and an insertion heuristic algorithm are suggested to obtain near optimal solutions. Computational experiments indicate that the presented models and algorithms are effective to solve the problems.     

Berth scheduling by customer service differentiation: A multi-objective approach

In this paper the discrete and dynamic berth allocation problem is formulated as a multi-objective combinatorial optimization problem where vessel service is differentiated upon based on priority agreements. A genetic algorithms based heuristic is developed to solve the resulting problem. A number of numerical experiments showed that the heuristic performed well in solving large, real life instances. The heuristic provided a complete set of solutions that enable terminal operators to evaluate various berth scheduling policies and select the schedule that improves operations and customer satisfaction. The proposed algorithm outperformed a state of the art metaheuristic and provided improved results when compared to the weighted approach.     

An effective genetic algorithm for the fleet size and mix vehicle routing problems

This paper studies the fleet size and mix vehicle routing problem (FSMVRP), in which the fleet is heterogeneous and its composition to be determined. We design and implement a genetic algorithm (GA) based heuristic. On a set of twenty benchmark problems it reaches the best-known solution 14 times and finds one new best solution. It also provides a competitive performance in terms of average solution.     

Arc routing problems to restore connectivity of a road network

After a disaster, restoring accessibility in the affected area is critical for response operations. We study two arc routing problems for clearing blocked roads. The first problem minimizes the time to reconnect the road network, while the second maximizes the total benefit gained by reconnecting network components within a time limit. For each problem, we develop a mixed integer programming formulation and two versions of a heuristic algorithm. We conduct computational experiments on Istanbul data and instances adapted from the literature. The heuristics achieve near-optimal or optimal solutions quickly in most of the tested instances.     

The simultaneous berth and quay crane allocation problem

This paper addresses efficient berth and crane allocation scheduling at a multi-user container terminal. First, we introduce a formulation for the simultaneous berth and crane allocation problem. Next, by employing genetic algorithm we develop a heuristic to find an approximate solution for the problem. The fitness value of a chromosome is obtained by crane transfer scheduling across berths, which is determined by a maximum flow problem-based algorithm based on a berth allocation problem solution defined by the chromosome. The results of numerical experiments show that the proposed heuristic is applicable to solve this difficult but essential terminal operation problem.     

Containership routing with time deadlines and simultaneous deliveries and pick-ups

In this paper we seek to determine optimal routes for a containership fleet performing pick-ups and deliveries between a hub and several spoke ports. A capacitated vehicle routing problem with pick-ups, deliveries and time deadlines is formulated and solved using a hybrid genetic algorithm for establishing routes for a dedicated containership fleet. Results on the performance of the algorithm and the feasibility of the approach show that a relatively small fleet of containerships could provide efficient services within deadlines. Moreover, through sensitivity analysis we discuss performance robustness and consistency of the developed algorithm under a variety of problem settings and parameters values.     

基于随机机会约束的空车调整模型的研究

通过对比空车调整问题的确定性模型与实际问题之间的差异，提出一类随机机会约束模型来模拟实际空车调整问题。通过引入概率模拟实际问题中的不确定因素，将确定性模型转化为不确定性模型，以使模型能更准确的反映实际，并将经济学指标作为评价标准。通过遗传算法求解算例，表明模型和方法的有效性。     

Liner hub-and-spoke shipping network design

This paper proposes a liner hub-and-spoke shipping network design problem by introducing the concept of a main port, as well as some container shipping constraints such as multi-type container shipment and transit time constraints, which are seldom considered in the previous studies. It develops a mixed-integer programming model with nonconvex multi-linear terms for the proposed problem. An efficient genetic algorithm embedded with a multi-stage decomposition approach is developed to solve the model. Numerical experiments are carried out to assess the effectiveness of the proposed model and the efficiency of the proposed algorithm.     

A memetic algorithm for the open capacitated arc routing problem

In this paper, an open capacitated arc routing problem (OCARP) is defined and considered. The OCARP seeks to find a set of minimum-cost open routes that can serve the tasks (i.e., required arcs) of a given graph, subject to the vehicle capacity and travel distance. A mathematical programming formulation and a lower bound are established. An effective memetic algorithm is developed for solving the OCARP. Computational experiments demonstrate that the proposed algorithm can produce high quality solutions within a reasonable computational time span, and the proposed memetic algorithm is superior to the classical genetic algorithm in solution quality.     

A hybrid parallel genetic algorithm for yard crane scheduling

This paper aims at postulating a novel strategy in terms of yard crane scheduling. In this study, a dynamic scheduling model using objective programming for yard cranes is initially developed based on rolling-horizon approach. To resolve the NP-complete problem regarding the yard crane scheduling, a hybrid algorithm, which employs heuristic rules and parallel genetic algorithm (PGA), is then employed. Then a simulation model is developed for evaluating this approach. Finally, numerical experiments on a specific container terminal yard are used for system illustration. Computational results suggest that the proposed method is able to solve the problem efficiently.     

双线铁路列车调度阶段计划自动调整的遗传算法

列车运行调整是一类NP完全问题,在借鉴国内外专家对铁路列车运行自动调整研究成果的基础上,建立双线铁路列车调度阶段计划自动调整数学模型,并给出相关约束表达式。根据遗传算法原理,对阶段计划自动调整模型进行优化,采用罚函数法对约束条件进行处理,建立基于惩罚函数的适应度函数,采用交叉、变异等技术给出遗传算法的基本求解步骤。     

Multi-objective optimization for planning liner shipping service with uncertain port times

This paper considers a joint tactical planning problem for the number of ships, the planned maximum sailing speed, and the liner service schedule in order to simultaneously optimize the expected cost, the service reliability and the shipping emission in the presence of port time uncertainty. The problem is formulated into a stochastic multi-objective optimization problem at the operational level. The relationships between the objectives and the decision variables are established. A simulation-based non-dominated sorting genetic algorithm is then presented to solve this problem. A case study is provided to illustrate the results and the application of the model.     

Mixed truck delivery systems with both hub-and-spoke and direct shipment

This paper studies a mixed truck delivery system that allows both hub-and-spoke and direct shipment delivery modes. A heuristic algorithm is developed to determine the mode of delivery for each demand and to perform vehicle routing in both modes of deliveries. Computational experiments are carried out on a large set of randomly generated problem instances to compare the mixed system with the pure hub-and-spoke system and the pure direct shipment system. The experiment results show that the mixed system can save around 10% total traveling distance on average as compared with either of the two pure systems.