Mismanagement of routing and deliveries between sites of the same company or toward external sites leads to consequences in the cost of transport. When shipping alternatives exist, the selection of the appropriate shipping alternative (mode) for each shipment may result in significant cost savings. In this paper, the authors examine a class of vehicle routing in which a fixed internal fleet is available at the warehouse in the presence of an external transporter. The authors describe hybrid Iterated Density Estimation Evolutionary Algorithm with 2-opt local search to determine the specific assignment of each tour to a private vehicle (internal fleet) or an outside carrier (external fleet). Experimental results show that this method is effective, allowing the discovery of new best solutions for well-known benchmarks.
TopIntroduction
In the last years, the price of fuels increased in a dramatic and spectacular way. This price increase obliges the companies to define their own program of transport and an effective management of use of their vehicles fleet. Any modern method of management of the increase of cost of fuel is equivalent to reducing the cost of transport and the planning of vehicle routing.
Numerous organizations are involved in the production and the distribution of goods. The manager has to make a decision and to specify the expeditions assigned to every truck for the delivery. Many manufacturers and distributors use private fleets, or the public carrier, with the purpose to collect or deliver goods for their installations. In addition, to offer greater control over goods movement private fleets may reduce costs over common carrier prices. Whereas common carriers typically require that shipments be processed at consolidation terminals, private fleets can transport shipments directly from origin to destination via multiple stop routes.
It is necessary to cultivate the interest in the selection of service of trucks because it has a particular impact on the organization which uses private vehicles, especially that the decision-makers are responsible for the use of the fleet and the setting of strategies who determines the balance between the public carrier and carrier's private use. If private vehicles are used, routing the vehicles for best utilization, sizing the vehicles and determining the required number of common choice must be made. The rate negotiation, shipment consolidation and routing are important considerations to use a common carrier. Owing to his scale economies, the common carrier may be able to offer a lower price for small shipments in particular. As mentioned in the literature we show that the success stories of the operations research community is derived from the Vehicle Routing Problem (VRP). The interplay between theory and practice is recognized as a major driving force for this success.
Despite its wealth and abundance of work that are devoted to him, the Vehicle Routing Problem with Private fleet and common Carrier (VRPPC) represent only a subset of a larger family known as VRP. It is one of the optimization problems most studied. This problem holds the attention of several researchers, and everywhere in the world, since many years. Several authors have made a literature review that deal with VRP these include those of Clarke and Wright (1964) which propose a saving heuristic to solve this variant of problem. A state of the art is proposed by Bodin et al. (1983) with purpose to give a good review for the Routing and scheduling of vehicles and crews.
Laporte (1992a, 1992b) studied the vehicle routing and proposed an overview of exact and approximate algorithms to solve the TSP and VRP. Toth and Vigo (2002) addressed the VRP, the authors in this book collected contributions from renowned experts on vehicle scheduling, who describe the main algorithms built for the VRP over the last 40 years. Like other authors, Golden et al. (1984) presented the VRP as problem easy to explain but difficult to solve.
More specifically, two types of problems have been addressed in literature: the VRP with limited fleet and the VRP with private fleet and common carrier. Several authors have studied the vehicle routing problem with limited fleet.
Osman and Salhi (1996) proposed local search strategies to solve the vehicle fleet mix problem. The Tabu Search (TS) heuristic is proposed to solve the heterogeneous fleet vehicle routing problem in the paper of Gendreau et al. (1999). Taillard (1999) implemented a heuristic column generation method (HCG) to solve the Heterogeneous fixed fleet vehicle routing problem (HFFVRP). Tarantilis et al. (2004) introduce a new metaheuristic called Back-tracking Adaptive Threshold Accepting (BATA) in order to solve the HFFVRP. A column generation method to solve the Heterogeneous fleet VRP is proposed by Choi and Tcha (2007). Li et al. (2007) developed a record-to-record travel algorithm for the HFFVRP. They have built an integer programming model and solved the linear relaxation by column generation. Recently, Euchi and Chabchoub (2010) implemented a hybrid tabu search to solve the heterogeneous fixed fleet vehicle routing problem, this metaheuristic produced very competitive results in the literature.