A decomposition-based iterative optimization algorithm for traveling salesman problem with drone

This study investigates a new delivery problem that has emerged after the attempts of several e-commerce and logistics firms to deploy drones in their operations to increase efficiency and reduce delivery times. In this problem, a delivery truck that carries a drone on its roof serves customers in coordination with a drone. The drone is considered to complement the truck due to its cost-efficiency and ability to access difficult terrains and to travel without exposure to congestion. This study presents an iterative algorithm that is based on a decomposition approach to minimize delivery completion time. In the first stage of the proposed methodology, the truck route and the customers assigned to the drone are determined. In the second stage, a mixed-integer linear programming model is solved to optimize the drone route by fixing the routing and the assignment decisions that are made in the first stage. Beginning with the shortest truck route, the assignment and the routing decisions are iteratively improved. The solution times of our algorithm are compared with the solution times of the state-of-the-art formulations that are solved by CPLEX. The results demonstrate that our algorithm yields shorter solution times for the instances that we generated with the specified parameters. An optimization-based heuristic algorithm, which obtains solutions for medium-sized instances, is developed by reducing the feasible search area.     

Solution methods for the taxi pooling problem

In Taiwan, taxi pooling is currently performed by some taxi companies using a trial-and-error experience-based method, which is neither effective nor efficient. There is, however, little in the literature on effective models and solution methods for solving the taxi pooling problem. Thus, in this study we employ network flow techniques and a mathematical programming method to develop a taxi pooling solution method. This method is composed of three models. First, a fleet routing/scheduling model is constructed to produce fleet/passenger routes and schedules. A solution algorithm, based on Lagrangian relaxation, a sub-gradient method and a heuristic to find the upper bound of the solution, is proposed to solve the fleet routing/scheduling model. Then, two single taxi-passenger matching models are constructed with the goals of decreasing number of passenger transfers and matching all passengers and taxis. These two taxi-passenger matching models are directly solved using a mathematical programming solver. For comparison with the solution method, we also develop another heuristic by modifying a heuristic recently proposed for solving a one-to-many taxi pooling problem. The performance of the solution method and the additional heuristic are evaluated by carrying out a case study using real data and suitable assumptions. The test results show that these two solution methods could be useful in practice.     

A bilevel flow model for hazmat transportation network design

In this work we consider the following hazmat transportation network design problem. A given set of hazmat shipments has to be shipped over a road transportation network in order to transport a given amount of hazardous materials from specific origin points to specific destination points, and we assume there are regional and local government authorities that want to regulate the hazmat transportations by imposing restrictions on the amount of hazmat traffic over the network links. In particular, the regional authority aims to minimize the total transport risk induced over the entire region in which the transportation network is embedded, while local authorities want the risk over their local jurisdictions to be the lowest possible, forcing the regional authority to assure also risk equity. We provide a linear bilevel programming formulation for this hazmat transportation network design problem that takes into account both total risk minimization and risk equity. We transform the bilevel model into a single-level mixed integer linear program by replacing the second level (follower) problem by its KKT conditions and by linearizing the complementary constraints, and then we solve the MIP problem with a commercial optimization solver. The optimal solution may not be stable, and we provide an approach for testing its stability and for evaluating the range of its solution values when it is not stable. Moreover, since the bilevel model is difficult to be solved optimally and its optimal solution may not be stable, we provide a heuristic algorithm for the bilevel model able to always find a stable solution. The proposed bilevel model and heuristic algorithm are experimented on real scenarios of an Italian regional network.     

Truck backhauling on two terminal networks

Truck backhauling reduces empty truck-miles by having drivers haul loads on trips back to their home terminal. This paper 1) examines the impact on backhauling opportunities of terminal locations and directional imbalances in the flow of freight from the terminals, and 2) develops a method for determining which truckloads should be backhauled. Backhauling is studied for two terminals sending full truckloads to many customers under steady-state conditions. This research develops two backhauling models. The first is a continuous model that makes simplifying assumptions about customer locations and travel distances. It results in formulae showing that 1) savings from backhauling increase at a decreasing rate as the directional flow of freight between two terminals becomes more balanced and 2) backhauling is an important, but often ignored, factor in terminal (e.g. trucking terminal, warehouse, or plant) location and supplier selection decisions. The second model is a more general discrete model that determines which loads should be backhauled to minimize empty truck-miles.     

Dynamic charging infrastructure deployment for plug-in hybrid electric trucks

Inspired by the rapid development of charging-while-driving (CWD) technology, plans are ongoing in government agencies worldwide for the development of electrified road freight transportation systems through the deployment of dynamic charging lanes. This en route method for the charging of plug-in hybrid electric trucks is expected to supplement the more conventional charging technique, thus enabling significant reduction in fossil fuel consumption and pollutant emission from road freight transportation. In this study, we investigated the optimal deployment of dynamic charging lanes for plug-in hybrid electric trucks. First, we developed a multi-class multi-criteria user equilibrium model of the route choice behaviors of truck and passenger car drivers and the resultant equilibrium flow distributions. Considering that the developed user equilibrium model may have non-unique flow distributions, a robust deployment of dynamic charging lanes that optimizes the system performance under the worst-case flow distributions was targeted. The problem was formulated as a generalized semi-infinite min-max program, and a heuristic algorithm for solving it was proposed. This paper includes numerical examples that were used to demonstrate the application of the developed models and solution algorithms.     

Allocating railroad maintenance funds by solving binary knapsack problems with precedence constraints

The United States is faced with allocating funds from a limited budget to the repair or replacement of railroad track segments on military bases. The problem can be modeled as a very large binary knapsack problem having a single budget constraint and multiple precedence constraints. A procedure has been developed to convert this original problem into an equivalent knapsack problem with a single constraint and significantly fewer variables. The new knapsack problem, still too large to be solved optimally, is then solved efficiently by a heuristic which provides answers within a few percent of optimality. Furthermore, the quality of the solution improves with the size of the problem.     

Testing and evaluation of a multi-commodity multi-modal network flow model for disaster relief management

The results of the testing of an optimization model in disaster relief management are presented. The problem is a large-scale multi-commodity, multi-modal network flow problem with time windows. Due to the nature of this problem, the size of the optimization model grows extremely rapidly as the number of modes and/or commodities increase. The formulation is based on the concept of a time-space network. Two heuristic algorithms are developed. One exploits an inherent network structure of the problem with a set of side constraints and the other is an interactive fix-and-run heuristic. The findings of the model-testing and a wide range of sensitivity analyses using an artificially generated data set are presented. Both solution procedures prove to be efficient and effective in providing close to optimal solutions.     

The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems

Most of the studies address issues relating to the delivery from satellites to customers, which is throughout the end part of the linehaul-delivery system. Differing from the long-term strategic problems including the two-echelon vehicle routing problem (2E-VRP), the two-echelon location routing problem (2E-LRP) and the truck and trailer routing problem (TTRP) which make location decisions in depots or satellites, the paper introduces a short-term tactical problem named the two-echelon time-constrained vehicle routing problem in linehaul-delivery systems (2E-TVRP) that does not involve location decisions. The linehaul level and the delivery level are linked through city distribution centers (CDCs) located on the outskirts of cities. The 2E-TVRP has inter-CDC linehaul on the first level and urban delivery from CDCs to satellites on the second level. Vehicle routes on different levels are interacted by time constraints. A mixed integer nonlinear programming model for the 2E-TVRP is put forward, and a mixed integer linear programming model is used as the benchmark model. The Clarke and Wright savings heuristic algorithm (CW) improved by a local search phase is adopted. The 2E-TVRP formulations and the heuristic algorithm are tested by using 140 randomly-generated instances with up to 10 CDCs and 500 satellites. The computational results indicate that the heuristic can effectively solve various instances of the 2E-TVRP.     

Green supply chain network design to reduce carbon emissions

We consider a supply chain network design problem that takes CO₂ emissions into account. Emission costs are considered alongside fixed and variable location and production costs. The relationship between CO₂ emissions and vehicle weight is modeled using a concave function leading to a concave minimization problem. As the direct solution of the resulting model is not possible, Lagrangian relaxation is used to decompose the problem into a capacitated facility location problem with single sourcing and a concave knapsack problem that can be solved easily. A Lagrangian heuristic based on the solution of the subproblem is proposed. When evaluated on a number of problems with varying capacity and cost characteristics, the proposed algorithm achieves solutions within 1% of the optimal. The test results indicate that considering emission costs can change the optimal configuration of the supply chain, confirming that emission costs should be considered when designing supply chains in jurisdictions with carbon costs.     

Liner shipping network design with emission control areas: A genetic algorithm-based approach

To curb emissions, containerized shipping lines face the traditional trade-off between cost and emissions (CO₂ and SO_x) reduction. This paper considers this element in the context of liner service design and proposes a mixed integer linear programming (MILP) model based on a multi-commodity pickup and delivery arc-flow formulation. The objective is to maximize the profit by selecting the ports to be visited, the sequence of port visit, the cargo flows between ports, as well as the number/operating speeds of vessels on each arc of the selected route. The problem also considers that Emission Control Areas (ECAs) exist in the liner network and accounts for the vessel carrying capacity. In addition to using the MILP solver of CPLEX, we develop in the paper a specific genetic algorithm (GA) based heuristic and show that it gives the possibility to reach an optimal solution when solving large size instances.     

Capacitated maximum covering location models: Formulations and solution procedures

This paper presents two formulations and two solution procedures for a capacitated maximum covering location problem. In the first formulation, the problem is presented as a mixed-interger linear programming model which maximizes covered demand. In the second model, the objective function maximizes the weighted covered demand while at the same time minimizing the average distance from the uncovered demands to the located facilities. The second formulation attempts to account for the assignment of the demand which is not “covered” to located facilities which have excess capacity. This assignment is very important, especially for locating emergency service facilities. Two heuristic procedures are proposed to solve these models. These are based on greedy adding technique and Lagrangian relaxation. At each iteration, the demands are allocated to the facilities using an out-of-kilter method. The performance of the solution techniques are compared to the optimal solutions in a variety of test problems.     

Ferry service network design: optimal fleet size,routing, and scheduling

The study formulated a ferry network design problem by considering the optimal fleet size, routing, and scheduling for both direct and multi-stop services. The objective function combines both the operator and passengers’ performance measures. Mathematically, the model is formulated as a mixed integer multiple origin–destination network flow problem with ferry capacity constraints. To solve this problem of practical size, this study developed a heuristic algorithm that exploits the polynomial-time performance of shortest path algorithms. Two scenarios of ferry services in Hong Kong were solved to demonstrate the performance of the heuristic algorithm. The results showed that the heuristic produced solutions that were within 1.3% from the CPLEX optimal solutions. The computational time is within tens of seconds even for problem size that is beyond the capability of CPLEX.     

Flexible feeder transit route design to enhance service accessibility in urban area

To improve the accessibility of transit system in urban areas, this paper presents a flexible feeder transit routing model that can serve irregular‐shaped networks. By integrating the cost efficiency of fixed‐route transit system and the flexibility of demand responsive transit system, the proposed model is capable of letting operating feeder busses temporarily deviate from their current route so as to serve the reported demand locations. With an objective of minimizing total bus travel time, a new operational mode is then proposed to allow busses to serve passengers on both street sides. In addition, when multiple feeder busses are operating in the target service area, the proposed model can provide an optimal plan to locate the nearest one to response to the demands. A three‐stage solution algorithm is also developed to yield meta‐optimal solutions to the problem in a reasonable amount of time by transforming the problem into a traveling salesman problem. Numerical studies have demonstrated the effectiveness of the proposed model as well as the heuristic solution approach. Copyright © 2015 John Wiley & Sons, Ltd.     

A model and a solution algorithm for airport common use check-in counter assignments

In this research we develop an integer programming model to assist airport authorities to assign common use check-in counters. Due to the many complicated factors that have to be considered in such a model, the problem size is expected to be huge, making its solution difficult and therefore not applicable to the real world. Therefore, we develop a heuristic method, containing three heuristic models, to solve the model. These heuristic models are formulated as zero–one integer programs that can be solved using the simplex method and the branch-and-bound technique. To test how well the proposed models and the solution method may be applied in the real world, we perform a case study concerning the operations of a major airport in Taiwan.     

A multiobjective model for maximizing fleet availability under the presence of flight and maintenance requirements

Every aircraft, military or civilian, must be grounded for maintenance after it has completed a certain number of flight hours since its last maintenance check. In this paper, we address the problem of deciding which available aircraft should fly and for how long, and which grounded aircraft should perform maintenance operations, in a group of aircraft that comprise a combat unit. The objective is to achieve maximum availability of the unit over the planning horizon. We develop a multiobjective optimization model for this problem, and we illustrate its application and solution on a real life instance drawn from the Hellenic Air Force. We also propose two heuristic approaches for solving large scale instances of the problem. We conclude with a discussion that gives insight into the behavior of the model and of the heuristics, based on the analysis of the results obtained.     

A Lagrangian relaxation based heuristic for the consolidation problem of airfreight forwarders

International air cargo is an operation-intensive industry, involving complex procedures and many players. As an important player, airfreight forwarders need to consolidate the collected goods skillfully in order to satisfy the requirements of the shippers and, at the same time minimize the expense charged by the airlines. However, the air cargo rate structure is very complicated, making the consolidation a difficult mixed-integer programming problem for the airfreight forwarder. In this paper, the consolidation problem is first transformed into a well-known set covering problem by treating a feasible consolidated shipment as a set. Lagrangian Relaxation is used as the backbone to develop a recursive heuristic algorithm. Based on the numerical experiment, the heuristic algorithm generates solutions very close to optimality. In particular, a sensitivity analysis is performed with respect to the degree of concavity. The results suggest that the solution algorithm can be used as a core module of the decision support system for air cargo consolidation.     

Optimal shipment decisions for an airfreight forwarder: Formulation and solution methods

We study the freight forwarder’s shipment planning problem in an airfreight forwarding network where a set of cargo shipments have to be transported to given destinations. We provide mixed integer programming formulations that use piecewise-linear cargo rates and account for volume and weight constraints, flight departure/arrival times, as well as shipment-ready times.After exploring the solution of such models using CPLEX, we devise two solution methodologies to handle large problem sizes. The first is based on Lagrangian relaxation, where the problems decompose into a set of knapsack problems and a set of network flow problems. The second is a local branching heuristic that combines branching ideas and local search. The two approaches show promising results in providing good quality heuristic solutions within reasonable computational times, for difficult and large shipment consolidation problems.     

A hybrid heuristic strategy for liquefied natural gas inventory routing

As liquefied natural gas (LNG) steadily grows to be a common mode for commercializing natural gas, LNG supply chain optimization is becoming a key technology for gas companies to maintain competitiveness. This paper develops methods for improving the solutions for a previously stated form of an LNG inventory routing problem (LNG-IRP). Motivated by the poor performance of a Dantzig-Wolfe-based decomposition approach for exact solutions, we develop a suite of advanced heuristic techniques and propose a hybrid heuristic strategy aiming to achieve improved solutions in shorter computational time. The heuristics include two phases: the advanced construction phase is based on a rolling time algorithm and a greedy randomized adaptive search procedure (GRASP); and the solution improvement phase is a series of novel MIP-based neighborhood search techniques. The proposed algorithms are evaluated based on a set of realistic large-scale instances seen in recent literature. Extensive computational results indicate that the hybrid heuristic strategy is able to obtain optimal or near optimal feasible solutions substantially faster than commercial optimization software and also the previously proposed heuristic methods.     

Modeling transit technology selection in a linear transportation corridor

This paper proposes an analytical model for investigating transit technology selection problem from a perspective of transit authority. Given a transit technology alternative (e.g., metro, light rail transit, or bus rapid transit), the proposed model aims to maximize the social welfare of the transit system by determining the optimal combination of transit line length, number of stations, station location (or spacing), headway, and fare. In the proposed model, the effects of passenger demand elasticity and capacity constraint are explicitly considered. The properties of the model are examined analytically, and a heuristic solution procedure for determining the model solution is presented. By comparing the optimized social welfare for different transit technology alternatives, the optimal transit technology solution can be obtained together with critical population density. On the basis of a simple population growth rate formula, optimal investment timing of a new transit technology can be estimated. The proposed methodology is illustrated in several Chinese cities. Insightful findings are reported on the interrelation among transit technology selection, population density, transit investment cost, and transit line parameter design as well as the comparison between social welfare maximization and profit maximization regimes. Copyright © 2014 John Wiley & Sons, Ltd.     

Robust models for transportation service network design

In this paper robust models are presented for the transportation service network design problem, using the ferry service network design problem as an example application. The base assumption is that only the mean and an upper bound on the passenger demand are known. In one robust model, this information is supplemented by a lower bound on the demand, whereas in a second robust model, the assumption is made that the variance of the demand is known, in addition to the mean and upper bound. The relationship between the two models is investigated and characterized analytically. A case study using the ferry service in Hong Kong is provided to illustrate the models.