"A practical application of a long haul freight transportation problem with transhipments"
Jorge Isaac Pemberthy R., Juan Esteban Muriel Villegas and Juan Gabriel Villada O.

This work faces a long-haul, transnational, cross-border transportation problem with transshipments applied to a transportation carrier in Colombia, Latin America. The case study company has a combination of challenges that are still rare in the literature, such as time windows, a vast fleet and different transport regulations between different countries. The problem involves a combination of different variants of the Vehicle Routing Problem (VRP), including the Pickup and delivery problem (PDVRP), the Vehicle Routing Problem with Time Windows (VRPTW), the Heterogeneous Fleet Vehicle Routing Problem (HFVPR), the Multi Depot Vehicle Routing Problem (MDVRP), the Vehicle Routing Problem with Backhauls (VRPB) and the Roll-on Roll-off Vehicle Routing Problem (RRVRP). 

The problem consists on different sets of tractors and trailers sparsed in predefined in road network. This is the main difference with classical VRP’s, where the whole fleet is located at a single depot. The objective is to pick-up an order request from one location and deliver it to an-other location. An order consists in the transportation of a specified freight which must be fitted in a predetermined tractor size. A tractor may need a trailer or can be a rigid tractor (no trailer needed). The trailers can be wooden, cabined or flat beds. When a customer submits a request, it specifies the pickup and delivery locations, and a pickup time window. A tractor type is assigned to the request and a transshipment (if necessary) and pickup and delivery paths are known in advance. From this point several options are available. 

The objective is to reduce the number of empty vehicle journeys for both third party and company owned resources, achieving a greater loyalty of vehicle owners to the transport company since is one of the most significant resources that impacts transportation carriers in Colombia. Different constraints are represented by the diversity of regulations between countries that directly affect the transportation service like: difference in weight limit, Enabling transit of vehicles and trailers, Modalities of transport - Border crossing (Transfer, Transshipment, Direct). 

The problem is solved using a combination of strategies: simulation and a metaheuristic. The metaheuristic was tested using two heuristics to generate initial feasible solutions. This method generated better solutions than the method applied by the carrier, showing that significant gains can be obtained. The solution is divided in two stages: an initial stage generates feasible solutions using a combination of random generation with a nearest neighbor algorithm, assigning requests to resources (tractors and trailers). The second stage uses the result of the first stage as the initial solution and applies Simulated Annealing (SA) [5] with a combinatorial function. Its objective is to minimize the total empty distance in the planning horizon by selecting the best feasible solution. 

We applied the proposed algorithm to a real-world problem from the carrier company with 364 service requests with pickup and deliveries in two countries. The original fleet capacity consists of tractors and trailers sparse across the transportation network. The algorithm was implemented on Visual Basic for Applications with Ms Excel in an intel core i5 with 8GB of Ram. Using the simulation, we found the baseline value of the objective function to be 125,727 total empty km travelled. We then used our solution approach with the initial random with nearest neighbor algorithm obtaining a total empty travelled distance of 90,857 km (a 27.4% reduction). The algorithm found 3,599 solutions before reaching the best value of the objective function. The total computation time was 5.2 hours (18,694 seconds).