Minimum cost path problem for Plug-in Hybrid Electric Vehicles

We introduce a practically important and theoretically challenging problem: finding the minimum cost path for PHEVs in a road network with refueling and charging stations. We show that this problem is NP-complete and present a mixed integer quadratically constrained formulation, a discrete approximation dynamic programming heuristic, and a shortest path heuristic as solution methodologies. Practical applications of the problem in transportation and logistics, considering specifically the long-distance trips, are discussed in detail. Through extensive computational experiments, significant insights are provided. In addition to the charging infrastructure availability, a driver’s stopping tolerance arises as another critical factor affecting the transportation costs.     

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.     

基于启发式函数蚁群算法的VRP优化研究

车辆路径问题是一个NP难题,蚁群算法是求解诸如车辆路径安排等组合优化问题的有效工具,为此利用启发式函数对传统的蚁群算法进行改进和优化.并通过实例对该方法进行检验,其结果显示,启发式函数蚁群算法的性能,优于传统的蚁群算法.     

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.     

Scheduling technicians for planned maintenance of geographically distributed equipment

A real-world planned maintenance scheduling problem that exists at several business units within United Technologies Corporation (UTC) is addressed in this paper. The scheduling problem is formulated as a multiple tour maximum collection problem with time-dependent rewards and an adaptive memory tabu search heuristic is developed to solve it. The effectiveness of the proposed solution approach is examined using real-world problem instances supplied by UTC. Relevant upper bounds are derived for the application. Results of numerical experiments indicate that the proposed tabu search heuristic is able to obtain near optimal solutions for large-size (i.e., actual) problem instances in reasonable computation time.     

Heuristics for quay crane scheduling at indented berth

This paper discusses the quay crane scheduling problem at indented berth, an extension to the current quay crane scheduling problem in the field of container terminal operation. A mixed integer programming model by considering the unique features of the quay crane scheduling problem at indented berth is formulated. For solution, decomposition heuristic framework is developed and enhanced by Tabu search. To evaluate the performance of the proposed heuristic framework, a comprehensive numerical test is carried out and its results show the good quality of the proposed heuristic framework.     

A rolling planning horizon heuristic for scheduling agents with different qualifications

This paper presents an optimization model for the tour scheduling problem for agents with multiple skills and flexible contracts in check-in counters at airports. The objective is to minimize the total assignment costs subject to demand fulfillment and labor regulations. In order to solve this problem we develop a rolling planning horizon-based heuristic. Our heuristic is robust and provides near-optimal schedules within reasonable computation time for real-world cases, although the parameter selection is important to its performance. In addition, we discuss the impact of the skill distribution on the scheduling costs for several instances.     

Exact and heuristic methods to solve the berth allocation problem in bulk ports

In this paper, we study the dynamic hybrid berth allocation problem in bulk ports with the objective to minimize the total service times of the vessels. We propose two exact methods based on mixed integer programming and generalized set partitioning, and a heuristic method based on squeaky wheel optimization, explicitly considering the cargo type on the vessel. The formulations are compared through extensive numerical experiments based on instances inspired from real bulk port data. The results indicate that the set partitioning method and the heuristic method can be used to obtain near-optimal solutions for even larger problem size.     

An optimal approach for a set covering version of the refueling-station location problem and its application to a diffusion model

This article deals with the refueling-station location problem for alternative fuel vehicles in a traffic network. Alternative fuel vehicles can be characterized by the vehicle range that limits the travelable distance with fuel at full capacity. I propose an efficient formulation of the refueling-station location problem using an optimal property and prove that the problem is NP(Non-deterministic Polynomial)-complete in the strong sense. I consider a special case of the refueling-station location problem in which the construction costs are equal for all nodes. In this case, the problem is to determine refueling station locations to minimize the total number of stations, while making the possible multiple predetermined origin–destination round-trips. I propose an optimal algorithm applicable when no refueling stations currently exist in a traffic network and a dynamic programming based algorithm applicable when a set of refueling stations already exists. I apply the algorithms to a traffic network to study the diffusion of refueling stations and predict the speed and range of station establishment. The computational experiments show that the speed of diffusion depends on the vehicle range and the sequence of the origin–destination demands considered in the diffusion process.     

Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads

This paper addresses the routing problem with unpaired pickup and delivery with split loads. An interesting factor of our problem is that the quantity and place for pickup and delivery are decision variables in the network. We develop an easy-to-implement heuristic in order to gain an efficient and feasible solution quickly. Then, a local search algorithm based on the variable neighborhood search (VNS) method is developed to improve the performance of the heuristic. Computational results show that the proposed VNS method is able to obtain an optimal or near optimal solution in reasonable time for the formulated problem.     

A hybrid population heuristic for the heterogeneous vehicle routing problems

The heterogeneous vehicle routing problem (HVRP) plays an important role in supply chain logistics. Two variants of HVRP are treated in this paper: one with fixed and variable costs (HVRPFD), and the other with only variable cost (HVRPD). A hybrid population heuristic that is able to solve both variants is proposed, in which a population of solutions are progressively evolved by crossovers and local searches. Computational results on a set of eight benchmark test problems from literature show that the proposed heuristic produces excellent solutions in short computing times.     

A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling,with consideration of fleet assignment problem

One of the most important airline's products is to determine the aircraft routing and scheduling and fleet assignment. The key input data of this problem is the traffic forecasting and allocation that forecasts traffic on each flight leg. The complexity of this problem is to define the connecting flights when passengers should change the aircraft to reach the final destination. Moreover, as there exists various types of uncertainties during the flights, finding a solution which is able to absorb these uncertainties is invaluable. In this paper, a new robust mixed integer mathematical model for the integrated aircraft routing and scheduling, with consideration of fleet assignment problem is proposed. Then to find good solutions for large-scale problems in a rational amount of time, a heuristic algorithm based on the Simulated Annealing (SA) is introduced. In addition, some examples are randomly generated and the proposed heuristic algorithm is validated by comparing the results with the optimum solutions. The effects of robust vs non-robust solutions are examined, and finally, a hybrid algorithm is generated which results in more effective solution in comparison with SA, and Particle Swarm Optimization (PSO).     

Design of a rail transit line for profit maximization in a linear transportation corridor

This paper addresses the design problem of a rail transit line located in a linear urban transportation corridor. The service variables designed are a combination of rail line length, number and locations of stations, headway and fare. Two profit maximization models, which account for the effects of different transit pricing structures (flat and distance-based fare regimes), are proposed. In the proposed models, the effects of passenger demand elasticity and population density along the urban corridor are explicitly considered. The solution properties of the proposed models are explored and compared analytically, and the indifference condition for the two fare regimes in terms of the operator’s net profit is identified. A heuristic solution algorithm to solve the proposed models is presented. Numerical examples are provided to show the effects of the fare regimes, rail capital cost and urban configuration (in terms of urban population distribution and corridor length) on the design of the rail transit line and the profitability of the rail transit operations.     

The multi-period service territory design problem – An introduction,a model and a heuristic approach

In service territory design applications, a field service workforce is responsible for providing recurring services at their customers’ sites. We introduce the associated planning problem, which consists of two subproblems: In the partitioning subproblem, customers must be grouped into service territories. In the scheduling subproblem, customer visits must be scheduled throughout the multi-period planning horizon. The emphasis of this paper is put on the scheduling subproblem. We propose a mixed integer programming model for this subproblem and present a location-allocation heuristic. The results of extensive experiments on real-world instances show that the proposed heuristic produces high-quality solutions.     

Designing robust routes for demand-responsive transport systems

In this study, we propose an innovative concept for robust demand-responsive transportation (DRT) systems where vehicles may deviate from the planned route to accept late requests, which are unknown during the planning stage. We propose a new formulation of the problem as a stochastic mixed integer program and describe an efficient heuristic procedure that embeds a tabu search approach in a scheme for merging different scenario solutions. The computational results demonstrate the validity of the heuristic and provide useful managerial insights into DRT systems, thereby showing the value of incorporating uncertainty into the planning process.     

A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph

We study a time-constrained heterogeneous vehicle routing problem on a multigraph where parallel arcs between pairs of vertices represent different travel options based on criteria such as time, cost, and distance. We formulate the problem as a mixed-integer linear programming model and develop a tabu search heuristic that efficiently addresses computational challenges due to parallel arcs. Numerical experiments show that the heuristic is highly effective and that freight operators can achieve advantages in cost and customer service by considering alternative paths, especially when route duration limits are restrictive and/or when vehicles of smaller capacity are dispatched to serve remote customers.     

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.     

Comparing heuristic algorithms of the planar storage location assignment problem

This paper discusses the newly defined planar storage location assignment problem (PSLAP). We develop a mathematical programming model and GA-based and dynamic PSLAP heuristic algorithms for the solving procedure. Using the testing set, we compare the performance of GA-based and dynamic PSLAP heuristic algorithms. The mathematical programming model is utilized as a comparison criterion. The comparison results demonstrate that the dynamic PSLAP heuristic algorithm performs better than the other solving procedures. In addition, we describe simulation experiments conducted to investigate the effects of stock yard layout and production schedule instability on the operation of the block stock yard.     

The capacitated plant location problem with customers and suppliers matching

This paper introduces a new problem called the capacitated plant location problem with customer and supplier matching (CLCSM). The product distribution from plants to customers and the material supply from suppliers to plants are considered together. We merge a distribution trip and a supply trip into one triangular trip for saving allocation cost. Vehicles from plants visit a customer and a supplier for each trip. We provide a heuristic solution procedure based on Lagrangian relaxation. Computational results indicate that the proposed heuristic solution procedure is shown to be efficient yielding optimal or near-optimal solutions for randomly generated instances.     

铁路主要货运站能力适应性分析及对策研究

研究主要货运站的能力适应性，对于解决当前铁路点线能力不匹配的问题具有重要意义。通过对全路主要货运站货运设施、货运到发量、能力利用率和存在问题的摸底调查，分析了全路主要货运站存在的普遍问题和实施升级改造的必要性，结合我国货运改革和货运需求变化等形势，提出若干主要货运站适应发展的对策，并以长沙地区货运站搬迁改造为例进行分析。