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.     

An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem

This paper studies the heterogeneous fixed fleet vehicle routing problem (HFFVRP), in which the fleet is composed of a fixed number of vehicles with different capacities, fixed costs, and variable costs. Given the fleet composition, the HFFVRP is to determine a vehicle scheduling strategy with the objective of minimizing the total transportation cost. We propose a multistart adaptive memory programming (MAMP) and path relinking algorithm to solve this problem. Through the search memory, MAMP at each iteration constructs multiple provisional solutions, which are further improved by a modified tabu search. As an intensification strategy, path relinking is integrated to enhance the performance of MAMP. We conduct a series of experiments to evaluate and demonstrate the effectiveness of the proposed algorithm.     

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.     

The split delivery vehicle routing problem with minimum delivery amounts

In the vehicle routing problem, a fleet of vehicles must service the demands of customers in a least-cost way. By allowing multiple vehicles to service the same customer (i.e., splitting deliveries), substantial savings in travel costs are possible. However, split deliveries are often an inconvenience to the customer who would prefer to have demand serviced in a single visit. We consider the vehicle routing problem in which split deliveries are allowed only if a minimum fraction of a customer’s demand is serviced by a vehicle. We develop a heuristic method for solving this problem and report computational results on a wide range of problem sets.     

Constructing a routable retrospective transit timetable from a real-time vehicle location feed and GTFS

We describe a method for retroactively improving the accuracy of a General Transit Feed Specification (GTFS) package by using a real-time vehicle location data set provided by the transit agency. Once modified, the GTFS package contains the observed rather than the scheduled transit operations and can be used in research assessing network performance, reliability and accessibility. We offer a case study using data from the Toronto Transit Commission and find that substantial aggregate accessibility differences exist between scheduled and observed services. This ‘error’ in the scheduled GTFS data may have implications for many types of measurements commonly derived from GTFS data.     

A heuristic approach to logistics network design for end-of-lease computer products recovery

This paper discusses the logistics network design for end-of-lease computer products recovery by developing a deterministic programming model for systematically managing forward and reverse logistics flows. Due to the complexity of such network design problem, a two-stage heuristic approach is developed to decompose the integrated design of the distribution networks into a location–allocation problem and a revised network flow problem. The applicability of the proposed method is illustrated in a numerical study. Computational experiments demonstrate that high-quality solutions are obtained while modest computational overheads are incurred.     

A model for taxi pooling with stochastic vehicle travel times

Taxi pooling means the sharing of a taxi by more than one passenger with at least a semi-common route. Currently, a trial-and-error process is adopted, taking into account expected travel times, for taxi pooling, a method which is neither effective nor efficient. This is because stochastic disturbances arising from variations in the taxi travel times that occur in actual traveling are neglected. In the worst case scenario, where vehicle travel times fluctuate wildly during operations, the planned schedule can be disturbed enough to lose its optimality. Therefore, in this study, a network flow technique is used to construct a stochastic taxi pooling model incorporating stochastic vehicle travel times. A solution algorithm is also proposed to efficiently solve the problem. The performance of the proposed models and the use of the solution method in practice are evaluated by executing numerical tests using real data with suitable assumptions. The test results show that the stochastic model and the solution method could be useful references for practice.     

A decision support system for vehicle relocation operations in carsharing systems

This paper presents a novel three-phase optimization-trend-simulation (OTS) decision support system for carsharing operators to determine a set of near-optimal manpower and operating parameters for the vehicle relocation problem. Tested on a set of commercially operational data from a carsharing company in Singapore, the simulation results suggest that the manpower and parameters recommended by the OTS system lead to a reduction in staff cost of 50%, a reduction in zero-vehicle-time ranging between 4.6% and 13.0%, a maintenance of the already low full-port-time and a reduction in number of relocations ranging between 37.1% and 41.1%.     

A vehicle routing cost evaluation algorithm for the strategic analysis of radial distribution networks

This article presents a new algorithm, based on bin packing algorithms, that determines vehicle routing costs on networks with certain geographic characteristics. Requiring very little data and computation time, the algorithm is used to test the impact of adding flexibility to a retailer’s Canadian distribution operations. It is shown that it is possible to save 5–10% of vehicle routing costs by modifying shipping schedules.     

Conditions for electric vehicle taxi: A case study in the Greater Stockholm region

This study investigates the usability of electric vehicles (EVs) in a taxi company in Greater Stockholm, Sweden. By investigating cost and revenue data of both electric and conventional taxi vehicles, as well as by interviewing taxi drivers and carriers, an assessment has been made of the financial and operational implications of using EVs in a company’s taxi fleet. Both the drivers’ and the carriers’ perspectives have been examined. The main findings are that the investigated e-taxis have a similar or lower Total Cost of Ownership and slightly higher profitability than the investigated conventional taxis. For taxi drivers, using e-taxis implies more advanced planning and revenue service time being sacrificed for charging. However, certain customers’ preferences for EVs, as well as benefits such as corporate clients favoring e-taxis and a zero emission priority queuing system at Stockholm’s main international airport (partly) compensate for time devoted to charging. In order to facilitate increased use of e-taxis, more fast charging facilities should become available at strategic locations. Besides that, there are signs that carriers’ lack of information about the opportunities and consequences of shifting towards e-taxis hamper a wider deployment of e-taxis.     

A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows

For VRP with time windows (VRPTW) solved by conventional cluster-first and route-second approach, temporal information is usually considered with vehicle routing but ignored in the process of clustering. We propose an alternative approach based on spatiotemporal partitioning to solving a large-scale VRPTW, considering jointly the temporal and spatial information for vehicle routing. A spatiotemporal representation for the VRPTW is presented that measures the spatiotemporal distance between two customers. The resulting formulation is then solved by a genetic algorithm developed for k-medoid clustering of large-scale customers based on the spatiotemporal distance. The proposed approach showed promise in handling large scale networks.     

A column generation based approach for the Train Network Design Optimization problem

This paper investigates the Train Network Design Optimization problem arising from railroad industry which involves the integration of three inter-related decision sub-problems: train routing which is to identify origin, destination and itinerary for individual trains; block-to-train assignment detailing the block movements with trains and swaps between trains; and crew-to-train assignment specifying the crew services for train routes. A column generation based hierarchical approach with two stages is designed: the first stage generates a pool of promising train routes iteratively based on the crew segments by the column generation technique; and the second stage develops an integer linear programming model for the subsequent decisions including train route selection and block-to-train assignment. Numerical experiments with realistic test instances are conducted and the outcome demonstrates the capability of the proposed approach in solving the Train Network Design Optimization problem competently.     

A study of the airline boarding problem

The airline industry is currently under intense pressure to simultaneously increase efficiency, customer satisfaction, and profitability. The boarding process is one way to achieve this objective as it lends itself to adaptive changes. The purpose of this paper is to determine the most cost-effective way to board passengers and still maintain quality and customer satisfaction. We conclude that the best strategy is to use a non-traditional methodology of outside-in or some modification thereof. The findings suggest that airline managers should consider issues related to evenly distributing boarding activity throughout the aircraft, developing more effective policies for managing carry-on luggage, and using simultaneous loading through two doors.     

A GIS-based Bayesian approach for analyzing spatial–temporal patterns of intra-city motor vehicle crashes

This paper develops a GIS-based Bayesian approach for intra-city motor vehicle crash analysis. Five-year crash data for Harris County (primarily the City of Houston), Texas are analyzed using a geographic information system (GIS), and spatial–temporal patterns of relative crash risks are identified based on a Bayesian approach. This approach is used to identify and rank roadway segments with potentially high risks for crashes so that preventive actions can be taken to reduce the risks in these segments. Results demonstrate the approach is useful in estimating the relative crash risks, eliminating the instability of estimates while maintaining overall safety trends. The 3-D posterior risk maps show risky roadway segments where safety improvements need to be implemented. Results of GIS-based Bayesian mapping are also useful for travelers to choose relatively safer routes.     

Temporal dynamics in local vehicle ownership for Great Britain

This article explores the stability of local vehicle ownership rates in Great Britain using the technique of spatial Markov chain analysis. Non-spatial Markov chain processes describe the transition of neighbourhoods through levels of ownership with no regard to their neighbourhood context. In reality however, how a neighbourhood transitions to different levels of ownership could be influenced by its neighbourhood context. A spatial Markov chain accounts for this context by estimating transition properties that are conditioned on the surrounding neighbourhood. These spatial Markov chain properties are estimated using a long run census time series from 1971 to 2011 of household vehicle ownership rates in Great Britain. These processes show that there is different behaviour in how neighbourhoods transition between levels of ownership depending on the context of their surrounding neighbours. The general finding is that the spatial Markov process will lead to a greater homogeneity in levels of ownership in each locality, with neighbourhoods surrounded by relatively low ownership neighbourhoods taking longer than a non-spatial Markov process would suggest to transition to higher levels, whilst neighbourhoods of high ownership surrounded by high ownership neighbourhoods take longer to transition to lower levels. This work corroborates Tobler's first law of geography “Everything is related to everything else, but near things are more related than distant things” but also provides practical guidance. Firstly, in modelling ownership, spatial effects need to be tested and when present, accounted for in the model formulation. Secondly, in a policy context, the surrounding neighbourhood situation is important, with neighbourhoods having a tendency towards homogeneity of ownership levels. This allows for the effective planning of transport provision for local services. Thirdly, vehicle ownership is often used as a proxy for the social and aspirational nature of an area and these results suggest that these properties will persist for a prolonged period, possibly perpetuating and exacerbating differentials in society.     

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.     

The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics

An algorithm that can tackle time dependent vehicle routing problems with hard or soft time windows without any alteration in its structure is presented. Analytical and experimental results indicate that average computational time increases proportionally to the number of customers squared. New replicable test problems that capture the typical speed variations of congested urban settings are proposed. Solution quality, time window perturbations, and computational time results are discussed as well as a method to study the impact of perturbations by problem type. The algorithm efficiency and simplicity is well suited for urban areas where fast running times may be required.     

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.