Solving the truck and trailer routing problem based on a simulated annealing heuristic

In this study, we consider the application of a simulated annealing (SA) heuristic to the truck and trailer routing problem (TTRP), a variant of the vehicle routing problem (VRP). In the TTRP, some customers can be serviced by either a complete vehicle (that is, a truck pulling a trailer) or a single truck, while others can only be serviced by a single truck for various reasons. SA has seen widespread applications to various combinatorial optimization problems, including the VRP. However, to our best knowledge, it has not been applied to the TTRP. So far, all the best known results for benchmark TTRP instances were obtained using tabu search (TS). We applied SA to the TTRP and obtained 17 best solutions to the 21 benchmark TTRP benchmark problems, including 11 new best solutions. Moreover, the computational time required by the proposed SA heuristic is less than those reported in prior studies. The results suggest that SA is competitive with TS on solving the TTRP.     

A note on the truck and trailer routing problem

This study considers the relaxed truck and trailer routing problem (RTTRP), a relaxation of the truck and trailer routing problem (TTRP). TTRP is a variant of the well studied vehicle routing problem (VRP). In TTRP, a fleet of trucks and trailers are used to service a set of customers with known demands. Some customers may be serviced by a truck pulling a trailer, while the others may only be serviced by a single truck. This is the main difference between TTRP and VRP. The number of available trucks and available trailers is limited in the original TTRP but there are no fixed costs associated with the use of trucks or trailers. Therefore, it is reasonable to relax this fleet size constraint to see if it is possible to further reduce the total routing cost (distance). In addition, the resulting RTTRP can also be used to determine a better fleet mix. We developed a simulated annealing heuristic for solving RTTRP and tested it on 21 existing TTRP benchmark problems and 36 newly generated TTRP instances. Computational results indicate that the solutions for RTTRP are generally better than the best solutions in the literature for TTRP. The proposed SA heuristic is able to find better solutions to 18 of the 21 existing benchmark TTRP instances. The solutions for the remaining three problems are tied with the best so far solutions in the literature. For the 36 newly generated problems, the average percentage improvement of RTTRP solutions over TTRP solutions is about 5%. Considering the ever rising crude oil price, even small reduction in the route length is significant.     

Truck and trailer routing—Problems,heuristics and computational experience

In the truck and trailer routing problem (TTRP) the vehicle fleet consists of truck units and trailer units with some customers only accessible by truck. For that purpose trailers can be uncoupled en-route at customers where truck sub-tours are built. We discuss several variants of this specific rich vehicle routing problem (RVRP): the TTRP with and without the option of load transfer between truck and trailer as well as the requirement of time windows for delivery. We present computational experience with a simple and flexible hybrid approach which is based on local search and large neighborhood search as well as standard metaheuristic control strategies. This approach which has shown to be rather effective on several other RVRP-classes before can compete with complex state-of-the-art approaches with respect to speed and accuracy on the TTRP too.     

Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows

Motivated by a situation faced by infrastructure service providers operating in urban areas with accessibility restrictions, we study the truck and trailer routing problem with time windows (TTRPTW). In this problem the vehicle fleet consists of trucks and trailers which may be decoupled. A set of customers has to be served and some of the customers can only be accessed by the truck without the trailer. This gives rise to the planning of truck-and-trailer routes containing truck-only subroutes, in addition to truck-only routes and truck-and-trailer routes without subroutes. We propose a branch-and-price algorithm for the TTRPTW, using problem specific enhancements in the pricing scheme and alternative lower bound computations. We also tailor an adaptive large neighborhood search algorithm to the TTRPTW in order to obtain good initial columns. When compared to existing metaheuristic algorithms we obtain highly competitive results. Some instances with up to 100 customers are solved to optimality with the proposed branch-and-price algorithm.     

A GRASP with evolutionary path relinking for the truck and trailer routing problem

In the truck and trailer routing problem (TTRP) a heterogeneous fleet composed of trucks and trailers has to serve a set of customers, some only accessible by truck and others accessible with a truck pulling a trailer. This problem is solved using a route-first, cluster-second procedure embedded within a hybrid metaheuristic based on a greedy randomized adaptive search procedure (GRASP), a variable neighborhood search (VNS) and a path relinking (PR). We test PR as a post-optimization procedure, as an intensification mechanism, and within evolutionary path relinking (EvPR). Numerical experiments show that all the variants of the proposed GRASP with path relinking outperform all previously published methods. Remarkably, GRASP with EvPR obtains average gaps to best-known solutions of less than 1% and provides several new best solutions.     

A tabu search heuristic for the truck and trailer routing problem

Two new construction heuristics and a tabu search heuristic are presented for the truck and trailer routing problem, a variant of the vehicle routing problem. Computational results indicate that the heuristics are competitive to the existing approaches. The tabu search algorithm obtained better solutions for each of 21 benchmark problems.     

GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots

In the single truck and trailer routing problem with satellite depots (STTRPSD) a vehicle composed of a truck with a detachable trailer serves the demand of a set of customers reachable only by the truck without the trailer. This accessibility constraint implies the selection of locations to park the trailer before performing the trips to the customers. We propose two metaheuristics based on greedy randomized adaptive search procedures (GRASP), variable neighborhood descent (VND) and evolutionary local search (ELS) to solve this problem. To evaluate these metaheuristics we test them on a set of 32 randomly generated problems. The computational experiment shows that a multi-start evolutionary local search outperforms a GRASP/VND. Moreover, it obtains competitive results when applied to the multi-depot vehicle routing problem (MDVRP), that can be seen as a special case of the STTRPSD.     

A reliable opportunistic routing for smart grid with in-home power line communication networks

The topology of in-home power line communication (PLC) networks varies frequently, which makes traditional routing algorithms failure. To solve this problem, an end-to-end transmission time for remaining path (TTRP) metric-based opportunistic routing (TTRPOR) is proposed. Since a local broadcasting scheme is adopted, the algorithm can find the optimal path for forwarding packets in a dynamic PLC network. The closed-form of the outage probability for a PLC channel is derived to estimate the TTRP. It is proved that the average throughput can achieve maximum as the metric TTRP is utilized to sort candidate forwarding nodes. Numerical results show that the end-to-end throughput of networks with TTRPOR, outperforms that of the network adopting DSR and EXOR, especially for the case of varying-topology in-home PLC networks.     

A simulated annealing heuristic for the capacitated location routing problem

The location routing problem (LRP) is a relatively new research direction within location analysis that takes into account vehicle routing aspects. The goal of LRP is to solve a facility location problem and a vehicle routing problem simultaneously. We propose a simulated annealing (SA) based heuristic for solving the LRP. The proposed SALRP heuristic is tested on three sets of well-known benchmark instances and the results are compared with other heuristics in the literature. The computational study indicates that the proposed SALRP heuristic is competitive with other well-known algorithms.     

The customer-centric,multi-commodity vehicle routing problem with split delivery

In this paper, we present the Customer-centric, Multi-commodity Vehicle Routing Problem with Split Delivery (CMVRPSD) whose objective is to minimize total waiting time of customers in distributing multiple types of commodities by multiple capacitated vehicles. It is assumed that a customer's demand can be fulfilled by more than one vehicle. Two classes of decisions are involved in this problem: routing vehicles to customers and quantifying commodities to load and unload. The CMVRPSD can be applied to distributing commodities in customer-oriented distribution problems for both peacetime and disaster situations. The problem is formulated in two Mixed-Integer Linear Programming (MILP) models, and a heuristic method is proposed by adapting and synthesizing Simulated Annealing (SA) and Variable Neighborhood Search (VNS) for large-scale problems. Experimental results show that the proposed hybrid algorithm outperforms other applicable algorithms such as SA, VNS, and Nearest Neighborhood heuristic.     

Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing

This paper aims at minimizing the makespan of two batch-processing machines in a flow shop. The processing times and the sizes of the jobs are known and non-identical. The machines can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time among all the jobs in that batch. The problem under study is NP-hard for makespan objective. Consequently, a heuristic based on Johnson's algorithm and a simulated annealing (SA) algorithm is proposed. Random instances were generated to verify the effectiveness of the proposed approaches. The results obtained from SA were compared with the proposed heuristic and a commercial solver. The SA outperformed both the heuristic and the commercial solver. On larger problem instances, the heuristic outperformed the commercial solver.     

Heuristic methods for vehicle routing problem with time windows

This paper documents our investigation into various heuristic methods to solve the vehicle routing problem with time windows (VRPTW) to near optimal solutions. The objective of the VRPTW is to serve a number of customers within predefined time windows at minimum cost (in terms of distance travelled), without violating the capacity and total trip time constraints for each vehicle. Combinatorial optimisation problems of this kind are non-polynomial-hard (NP-hard) and are best solved by heuristics. The heuristics we are exploring here are mainly third-generation artificial intelligent (AI) algorithms, namely simulated annealing (SA), Tabu search (TS) and genetic algorithm (GA). Based on the original SA theory proposed by Kirkpatrick and the work by Thangiah, we update the cooling scheme and develop a fast and efficient SA heuristic. One of the variants of Glover's TS, strict Tabu, is evaluated and first used for VRPTW, with the help of both recency and frequency measures. Our GA implementation, unlike Thangiah's genetic sectoring heuristic, uses intuitive integer string representation and incorporates several new crossover operations and other advanced techniques such as hybrid hill-climbing and adaptive mutation scheme. We applied each of the heuristics developed to Solomon's 56 VRPTW 100-customer instances, and yielded 18 solutions better than or equivalent to the best solution ever published for these problems. This paper is also among the first to document the implementation of all the three advanced AI methods for VRPTW, together with their comprehensive results.     

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.     

Multiple cross-docks scheduling using two meta-heuristic algorithms

This paper considers a truck scheduling problem in a multiple cross docks while there is temporary storage in front of the shipping docks. Receiving and shipping trucks can intermittently move in and out of the docks during the time intervals between their task execution, in which trucks can enter to any of the cross docks. Thus, a mixed-integer programming (MIP) model for multiple cross docks scheduling is developed inspired by models in the body of the respective literature. Its objective is to minimize the total operation time or maximize the throughput of the cross-docking system. Moreover, additional concepts considered in the new method is multiple cross docks with a limited capacity. In this study, there are two types of delay times. The first type occurs when there is a shipping truck change and the second one occurs when the current shipping truck does not load any product from a certain receiving truck or temporary storage and waits until its needed products arrive at the shipping docks. To solve the developed model, two meta-heuristics, namely simulated annealing (SA) and firefly algorithms (FA), are proposed. In addition, a procedure for trucks scheduling in a state of a constant discrete firefly algorithm for the discrete adaptation has been proposed. The experimental design is carried out to tune the parameters of algorithms. Finally, the solutions obtained by the proposed SA and FA are compared.     

Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines

This article addresses a multi-stage flow shop scheduling problem with unrelated parallel machines. Some practical processing restrictions such as independent setup and dependent removal times are taken into account as well. The objective is to minimize total flow time in the system. A simulated annealing (SA)-based heuristic is proposed to solve the addressed problem in a reasonable running time. The heuristic begins on a well-designed initial solution generator; then a simulated annealing procedure is applied for further improvement of the solution. To assure the quality and efficiency of the solution for the proposed SA-based heuristic, certain mechanisms are developed and introduced into the heuristic. The computational experimental results show that the proposed SA-based heuristic performs well with respect to accuracy and efficiency of solution.     

A scalable method for DCLC problem using hierarchical MDP model

It is well known that the delay-constrained least-cost (DCLC) routing problem is NP-complete, hence various heuristic methods have been proposed for this problem. However, these heuristic methods have poor scalability as the network scale increases. In this paper we propose a new method based on the Markov Decision Process (MDP) theory and the hierarchical routing scheme to address the scalability issue of the DCLC routing problem. We construct a new two-level hierarchy MDP model and apply an infinite-horizon discounted cost model to the upper level for the end-to-end inter-domain link selection. Since the infinite-horizon discounted cost model is independent of network scale, the scalability problem is resolved. With the proposed model, we further give the algorithm of solving the optimal policy to obtain the DCLC routing. Simulation results show that the proposed method improves the scalability significantly.     

A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing

This paper presents an extension of a competitive vehicle routing problem with time windows (VRPTW) to find short routes with the minimum travel cost and maximum sale by providing good services to customers before delivering the products by other rival distributors. In distribution of the products with short life time that customers need special device for keeping them, reaching time to customers influences on the sales amount which the classical VRPs are unable to handle these kinds of assumptions. Hence, a new mathematical model is developed for the proposed problem and for solving the problem, a simulated annealing (SA) approach is used. Then some small test problems are solved by the SA and the results are compared with obtained results from Lingo 8.0. For large-scale problems, the, Solomon's benchmark instances with additional assumption are used. The results show that the proposed SA algorithm can find good solutions in reasonable time.     

Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times

This research deals with the single machine scheduling problem (SMSP) with uncertain job processing times. The single machine robust scheduling problem (SMRSP) aims to obtain robust job sequences with minimum worst-case total flow time. We describe uncertain processing times using intervals, and adopt an uncertainty set that incorporates a budget parameter to control the degree of conservatism. A revision of the uncertainty set is also proposed to address correlated uncertain processing times due to a number of common sources of uncertainty. A mixed integer linear program is developed for the SMRSP, where a linear program for determining the worst-case total flow time is integrated within the conventional integer program of the SMSP. To efficiently solve the SMRSP, a simple iterative improvement (SII) heuristic and a simulated annealing (SA) heuristic are developed. Experimental results demonstrate that the proposed SII and SA heuristics are effective and efficient in solving SMRSP with practical problem sizes.     

Simulated annealing heuristics for the dynamic facility layout problem

In today's economy, manufacturing plants must be able to operate efficiently and respond quickly to changes in product mix and demand. Therefore, this paper considers the problem of arranging and rearranging (when there are changes between the flows of materials between departments) manufacturing facilities such that the sum of the material handling and rearrangement costs is minimized. This problem is known as the dynamic facility layout problem (DFLP). In this paper, two simulated annealing (SA) heuristics are developed for the DFLP. The first SA heuristic (SA I) is a direct adaptation of SA to the DFLP. The second SA heuristic (SA II) is the same as SA I with a look-ahead/look-back strategy added. To test the performance of the heuristics, a data set taken from the literature is used in the analysis. The results obtained show that the proposed heuristics are very effective for the dynamic facility layout problem.     

Comparing descent heuristics and metaheuristics for the vehicle routing problem

Three improvement heuristics for the vehicle routing problem are considered: a descent heuristic and two metaheuristics Simulated Annealing and Tabu Search. In order to make an in-depth comparison of the performance of these improvement heuristics, their behavior is analyzed on a heuristic, time-sensitive level as well as on a parametric level. The design and the results of the experiments are outlined. The external validity of the conclusions is discussed.Scope and purposeTabu Search (TS) and Simulated Annealing (SA) have demonstrated to be appropriate metaheuristics for solving NP-hard combinatorial optimization problems, such as the vehicle routing problem with side-constraints. In order to compare the performances of both metaheuristics with each other and with a traditional descent implementation, a comparison of the best solution independent of computing times is fundamentally wrong because metaheuristics have no unambiguous stopping criteria, as opposed to traditional descent implementations.