Adaptive granular local search heuristic for a dynamic vehicle routing problem

The advance of communication and information technologies based on satellite and wireless networks have allowed transportation companies to benefit from real-time information for dynamic vehicle routing with time windows. During daily operations, we consider the case in which customers can place requests such that their demand and location are stochastic variables. The time windows at customer locations can be violated although lateness costs are incurred. The objective is to define a set of vehicle routes which are dynamically updated to accommodate new customers in order to maximize the expected profit. This is the difference between the total revenue and the sum of lateness costs and costs associated with the total distance traveled. The solution approach makes use of a new constructive heuristic that scatters vehicles in the service area and an adaptive granular local search procedure. The strategies of letting a vehicle wait, positioning a vehicle in a region where customers are likely to appear, and diverting a vehicle away from its current destination are integrated within a granular local search heuristic. The performance of the proposed approach is assessed in test problems based on real-life Brazilian transportation companies.     

Branch and bound algorithms for the bus evacuation problem

The bus evacuation problem (BEP) is a vehicle routing problem that arises in emergency planning. It models the evacuation of a region from a set of collection points to a set of capacitated shelters with the help of buses, minimizing the time needed to bring the last person out of the endangered region.     

A hierarchical algorithm for the planar single-facility location routing problem

Location routing problem (LRP) is an important logistical problem that comprises two of the main logistical drivers namely facility location and vehicle routing. In this paper, we focus on the planar single-facility LRP with Euclidean distance where the location of the facility can be anywhere in the space and not restricted to a given set of potential sites only as in the discrete case. A hierarchical heuristic-based method is put forward which continuously takes into account the information from the routing results while systematically improving the location using the end-points of the obtained routes. In addition, some enhancement schemes that include a set of local searches as well as diversification and intensification mechanisms are also incorporated into the search. The proposed method outperformed the existing approaches when tested on the data sets taken from the literature. Our approach produced nine new best results out of the fifteen in the literature besides being relatively robust when compared to the existing methods.     

A network transformation heuristic approach for the deviation flow refueling location model

In the early stages of development, alternative-fuel vehicles will tend to have shorter driving ranges than conventional vehicles, and the availability of stations will be limited. Given these conditions, it is important to consider the willingness of drivers to deviate to some extent from their shortest paths in order to refuel their vehicles and complete their trips. Previously, we proposed the deviation-flow refueling location model (DFRLM) for locating a given number of refueling facilities to maximize the total alternative-fuel vehicle flows that can be refueled by drivers traveling on or deviating from their shortest paths. On a real-world problem, however, the large number of possible deviations from each path and of combinations of facilities that can cover each path would make it extremely difficult to generate and solve the mixed-integer formulation. This paper develops heuristic algorithms for the DFRLM that overcome this difficulty through network transformation. Specifically, a greedy heuristic constructs and edits an artificial feasible network in which each node represents a station, origin, or destination, and each arc represents a feasible path between two nodes given the assumed driving range of vehicles. At each step of the greedy and greedy-substitution algorithms, the feasible network is edited and a shortest path algorithm is run, which determines whether each origin–destination round trip can be completed. This method allows any possible detour to be taken (up to some user-defined maximum) while also ensuring that drivers take the smallest possible detour. Computational experiments on a simple network and a real-world network for Florida show the heuristics to be efficient in solving the problems. Comparisons between the results of the DFRLM and the FRLM indicate that taking driver deviations into account in the model can have a significant effect on the locations chosen and demand covered.     

A heuristic rule for relocating blocks

One of the most important objectives of the storage and pickup operations in block stacking systems is to minimize the number of relocations during the pickup operation. This study suggests two methods for determining the locations of relocated blocks. First, a branch-and-bound (B&B) algorithm is suggested. Next, a decision rule is proposed by using an estimator for an expected number of additional relocations for a stack. The performance of the decision rule was compared with that of the B&B algorithm.     

Efficient location area planning for cellular networks with hierarchical location databases

Location area planning (LAP) is an important issue in the design of high-performance PCS networks. It could have a serious impact on the total mobility management cost of mobile terminals. Most of the previous works either explored the LAP problem as a 0–1 linear programming problem or used adopted techniques, such as simulated annealing, taboo search, and genetic algorithms [IEEE Trans. Vehicular Technol. 49 (2000) 1678; Proceedings of 1999 Vehicular Technology Conference, vol. 4, 1999, pp. 2119–2123; IEEE Vehicular Technol. Conf. 3 (1996) 1835; Proceedings of IEEE INFOCOM'01, Anchorage, Alaska, April 2001; IEEE Trans. Vehicular Technol. 47 (1998) 987], to derive a solution to minimize the location update cost. In this paper, we model and resolve the LAP problem as a set-covering problem. The main advantage of this approach is that it can adapt to the changing mobility patterns of the mobile terminals. We propose the set-covering-based location area planning (SCBLP) algorithm to minimize the total number of location updates, in which the cost-benefit functions are defined based on the coupling and cohesive functions among neighboring cells. We then apply SCBLP to the location database system with a hierarchical structure to further improve the overall system performance in searching and updating the location databases. Extensive simulation experiments have been conducted, and the experimental results show that our proposed algorithms can significantly reduce the location management costs, compared to the greedy algorithm and the random algorithm.     

Computational performances of a simple interchange heuristic for a scheduling problem with an availability constraint

This paper deals with a scheduling problem on a single machine with an availability constraint. The problem is known to be NP-complete and admits several approximation algorithms. In this paper we study the approximation scheme described in He et al. [Y. He, W. Zhong, H. Gu, Improved algorithms for two single machine scheduling problems, Theoretical Computer Science 363 (2006) 257–265]. We provide the computation of an improved relative error of this heuristic, as well as a proof that this new bound is tight. We also present some computational experiments to test this heuristic on random instances. These experiments include an implementation of the fully-polynomial time approximation scheme given in Kacem and Ridha Mahjoub [I. Kacem, A. Ridha Mahjoub, Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers and Industrial Engineering 56 (2009) 1708–1712].     

A construction and improvement heuristic for a liquefied natural gas inventory routing problem

We present a large scale ship routing and inventory management problem for a producer and distributor of liquefied natural gas (LNG). The problem contains multiple products, inventory and berth capacity at the loading port and a heterogeneous fleet of ships. The goal is to create an annual delivery program to fulfill the producer’s long-term contracts at minimum cost, while maximizing the revenue from selling LNG in the spot market. To solve this problem we have developed a construction and improvement heuristic (CIH).The CIH is a multi-start local search heuristic that constructs a set of solutions using a greedy insertion procedure. The solutions are then improved using either a first-descent neighborhood search, branch-and-bound on a mathematical formulation, or both. Tests on real-life instances show that the CIH provides good solutions in a short amount of time.     

The heuristic concentration-integer and its application to a class of location problems

We propose a new metaheuristic called heuristic concentration-integer (HCI). This metaheuristic is a modified version of the heuristic concentration (HC), oriented to find good solutions for a class of integer programming problems, composed by problems in which p   elements must be selected from a larger set, and each element can be selected more than once. These problems are common in location analysis. The heuristic is explained and general instructions for rewriting integer programming formulations are provided, that make the application of HCI to these problems easier. As an example, the heuristic is applied to the maximal availability location problem (MALP), and the solutions are compared to those obtained using linear programming with branch and bound (LP+B&B)$(\mathrm{LP}+\mathrm{B}\&\mathrm{B})$. For one-third of the instances of MALP, LP+B&B$\mathrm{LP}+\mathrm{B}\&\mathrm{B}$ can be allowed to run until the computer is out of memory without termination, while HCI can find good solutions to the same instances in a reasonable time. In one such case, LP-IP was allowed to run for nearly 100 times longer than HCI and HCI still found a better solution. Furthermore, HCI found the optimal solution in 33.3% of cases and had an objective value gap of less than 1% in 76% of cases. In 18% of the cases, HCI found a solution that is better than LP+B&B. Therefore, in cases where LP+B&B$\mathrm{LP}+\mathrm{B}\&\mathrm{B}$ is unreasonable due to time or memory constraints, HCI is a valuable tool.     

Efficient heuristics for wireless network tower placement

Over the last decade, telecommunications companies have invested nearly 100 billion dollars in the development of an impressive fiber optic backbone which is capable of transmitting data at incredible speeds. However, much of this backbone remains unused because of the data capacity bottleneck which exists at the user level. While various technologies have emerged to provide greater end-point capacity, many of these are of limited availability due to cost or technical considerations. One promising technology has been high-speed wireless service. Wireless service has the potential to provide widespread coverage, but the cost of developing the infrastructure such as antenna towers can be formidable. While models have been developed to assist in the planning for minimum cost tower placement, these models can be quite large and complex to solve. This paper explores alternate solution methods based on heuristic approaches which may allow for the solution of much larger tower placement problems.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.     

Hybrid method for a general optimal sensor scheduling problem in discrete time

In this paper, we consider a general class of optimal sensor scheduling problems in discrete time. There are N₁ sensors available for acquiring data so as to estimate the needed but unknown signal. Only N₂ out of the N₁ sensors can be turned on at any moment, while different weights can be assigned to different sensors. This problem is formulated as a discrete time deterministic optimal control problem involving both discrete and continuous valued controls. A computational method is developed for solving this discrete time deterministic optimal control problem based on a branch and bound method in conjunction with a gradient-based method. The branch and bound method is used to determine the optimal schedule of sensors, where a sequence of lower bound dynamic systems is introduced so as to provide effective lower bounds for the construction of the branching rules. Each of the branches is an optimal weight vector assignment problem and a gradient-based method is developed for solving this optimal control problem. For illustration, two numerical examples are solved.     

A heuristic method for two-stage hybrid flow shop with dedicated machines

This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines, in which the first stage contains a single common critical machine, and the second stage contains several dedicated machines. Each job must be first processed on the critical machine in stage one and depending on the job type, the job will be further processed on the dedicated machine of its type in stage two. The objective is to minimize the makespan. To solve the problem, a heuristic method based on branch and bound (B&B) algorithm is proposed. Several lower bounds are derived and four constructive heuristics are used to obtain initial upper bounds. Then, three dominance properties are employed to enhance the performance of the proposed heuristic method. Extensive computational experiments on two different problem categories each with various problem configurations are conducted. The results show that the proposed heuristic method can produce very close-to-optimal schedules for problems up to 100 jobs and five dedicated machines within 60 s. The comparisons with solutions of two other meta-heuristic methods also prove the better performance of the proposed heuristic method.     

Efficient handling of universally quantified inequalities

This paper introduces a new framework for solving quantified constraint satisfaction problems (QCSP) defined by universally quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and technology. We introduce a generic branch and prune algorithm to tackle these continuous CSPs with parametric constraints, where the pruning and the solution identification processes are dedicated to universally quantified inequalities. Special rules are proposed to handle the parameter domains of the constraints. The originality of our framework lies in the fact that it solves the QCSP as a non-quantified CSP where the quantifiers are handled locally, at the level of each constraint. Experiments show that our algorithm outperforms the state of the art methods based on constraint techniques. This paper is an extended version of a paper published at the SAC 2008 conference [15].     

A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock

This paper studies truck scheduling in a resource-constrained crossdock. The problem decides on the sequence of incoming and outgoing trucks at the dock doors of the crossdocking terminal, subject to the availability of crossdock resources including dock doors and material handling systems. The resources are assumed non-preemptive making it necessary to address the feasibility of the problem before its optimality as it might be entrapped in deadlock and no feasible solution is produced. The paper thus aims at developing an algorithmic approach capable of establishing solution feasibility for truck scheduling problem instances of various types and difficulty levels which at the same time can be readily implemented in an industrial setting. The proposed approach is a two-phase heuristic algorithm where in the first phase, a heuristic search is deployed to construct a feasible sequence of trucks for the assignment to dock doors and in the second, a rule-based heuristic is used to assign each sequenced truck to a proper dock door, subject to a limited number of forklifts, such that significant savings in the truck schedule length are achieved. Extensive experiments are conducted to evaluate the efficiency of the algorithm in terms of deadlock avoidance and solution quality. The evaluation is carried out against the solutions generated by the exact mathematical model of the problem and a constructive heuristic developed for a similar truck scheduling problem. Experimental results demonstrate that the proposed algorithm is robust in avoiding deadlock and generates feasible solutions for the instances where the other two approaches cannot. Furthermore, significant improvement in the solution quality is achieved by augmenting the algorithm to a re-starting heuristic.     

Solving the one-dimensional bin packing problem with a weight annealing heuristic

In this paper, we develop a new procedure that uses the concept of weight annealing to solve the one-dimensional bin packing problem. Our procedure is straightforward and easy to follow. We apply it to 1587 instances taken from benchmark problem sets and compare our results to those found in the literature. We find that our procedure produces very high-quality solutions very quickly and generates several new optimal solutions.     

A new heuristic for solving the p-median problem in the plane

This paper presents a new local search for solving the continuous p-median problem in the plane. The basic idea is to first find a good starting solution by overlaying the area containing the set of demand points with a grid and solving heuristically the location problem on this grid. The solution is then used as an initial point for running an improved version of Cooper's well-known alternating local search.     

A 2-phase algorithm for solving the single allocation p-hub center problem

The single allocation p-hub center problem is an NP-hard location–allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin–destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date.