Metaheuristic Approaches for Solving Truck and Trailer Routing Problems with Stochastic Demands: A Case Study in Dairy I...
Published: 01 January 2015
Mathematical Problems in Engineering,
See at publisher website
ABS Show/hide abstract
Manufacturers and service providers often encounter stochastic demand scenarios. Researchers have, thus far, considered the deterministic truck and trailer routing problem (TTRP) that cannot address ubiquitous demand uncertainties and/or other complexities. The purpose of this study is to model the TTRP with stochastic demand (TTRPSD) constraints to bring the TTRP model closer to a reality. The model is solved in a reasonable timeframe using data from a large dairy service by administering the multipoint simulated annealing (M-SA), memetic algorithm (MA), and tabu search (TS). A sizeable number of customers whose demands follow the Poisson probability distribution are considered to model and solve the problem. To make the solutions relevant, first, 21 special TTRPSD benchmark instances are modified for this case and then these benchmarks are used in order to increase the validity and efficiency of the aforementioned algorithms and to show the consistency of the results. Also, the solutions have been tested using sensitivity analysis to understand the effects of the parameters and to make a comparison between the best results obtained by three algorithms and sensitivity analysis. Since the differences between the results are insignificant, the algorithms are found to be appropriate and relevant for solving real-world TTRPSD problem.1. IntroductionThese days, complex customer demands are required to be satisfied by many companies. Therefore, a large number of companies are trying to achieve a high level of reliability, flexibility, and agility for different demands. As a result, supply chain management (SCM) has become a thought-provoking subject for various companies, seeking for a way out of efficiently improving their customer satisfaction. In a way, according to the position and role, supply chain is categorized into three classes; the outbound, intracompany, and inbound supply chain. As the network of supplies begins at the inbound supply chain, the role of this group is transporting the semifinished products or the raw materials to the site of manufacturing. The main concern of the intracompany supply chain, as the intermediary part, is with the flow of material in the site of manufacturing. Finally, the outbound supply chain is concerned with the delivery of final products to the customers . The inventory allocation and transportation are strongly considered in the outbound supply chain for minimizing the cost and satisfying the customers’ demands. One significant part of the supply chain management is providing the services or/and goods from a supply point to different destinations, which are geographically distributed with significant implications of economics. Aside from the cost of purchasing the goods, on the average and compared to the other relative activities, a higher percentage of the costs of logistics are absorbed by transportation. Therefore, efficiency improvement through the maximum usage of the necessities of transportation and decreasing the costs of transportation along with the improvement of services for customers are the frequent and significant decision analysis problems .Customers, warehouses, manufacturers, and suppliers are the main elements of a supply chain (SC), carrying the goods from the upstream to the downstream links of the chain. In a supply chain, there are four main business functions to be performed: purchasing, manufacturing, inventory, and distribution. The function of distribution includes two activities: the shipment of finished products from the companies to the locations of demand, and transportation of parts or raw materials from the suppliers to the companies .In order to manage a supply chain, a large number of business processes need to be carried out and many decisions are required to be made. Particular design versions of these general supply systems and inventory planning problems have been studied for a long time. It is pretty obvious that these main supply chain problems are greatly related. As the time goes by, more companies are awakened about their supply chain performance and how important it is that they improve this performance. They also have become aware of the competitive advantage of distribution operations, inventory, integration, and coordination of supplies. One of the main problems in supply chain management and logistics is the routing of a series of vehicles, which are assigned to transport goods from a warehouse to the customers or/and retailers. Since goods are hardly ever produced and consumed in one particular place, transportation is considered as a significant factor in the supply chain management.In this study, the supply chain is considered in terms of transportation and distribution. Due to the complexity, a large number of realistic solutions are disregarded. Any company in the world currently faces with a number of challenges in serving their customers. Transportation cost is considered to be the largest logistics expense for a vast number of firms and companies. Transportation is the area where costs should be diminished. This is a very bearing question, how servicing and manufacturing companies could successfully diminish transportation expenses without overshadowing customers’ satisfaction .It is a widely accepted principle that firms aiming to serve the customers scattered in a vast area should possess a servicing plan if they do not want to waste time and money. One of the best approaches to work out the arising problematic issues is to apply a special and unique method under the title of vehicle routing problem (VRP). Also, the truck and trailer routing problem (TTRP) is one of the widely studied and most important combinatorial optimization problems in VRP domain and because of its natural complications and efficacies in a large number of real world and supply chain management applications, it is finding its place in the transportation logistic.This paper discusses a real case study under TTRP in which demands are stochastic (TTRPSD) in nature. This work is an advancement of the well-known deterministic TTRP. TTRP is a variant of the vehicle routing problem (VRP). It is related to transporting manufacturing goods within a plant or between factory floors and delivering products to intended markets or customers. Indeed, VRP has been known as one of the most studied combinatorial optimization problems in the past few decades. It covers certain areas in practice and considers complexities to a reasonable extent such as stochastic VRP, multi depot VRP and TTRP [5–8]. Dantzig and Ramser  defined VRP as a generalized solution based on Travelling Salesman Problem (TSP) in 1959. After that many researchers have extended this concept to make it useful in diverse areas. During the last two decades, some constraints such as time window, travel and service time were added to the VRP. Due to some other practical issues, such as narrow roads and bridges in village or government restrictions, maneuvering a complete vehicle sometime appears to be difficult - the traditional VRP approach is found inadequate and these issues are considered in TTRP model. In general, TTRP is more extensive than VRP and can cover more real life aspects since some limitations in VRP as mentioned above can be considered in TTRP.In TTRP, the customers may be serviced either by a single truck or complete vehicle (truck with a trailer). This feature is usually ignored in VRP. However, because of some obstacles that appear in real-life situations, such as road conditions, market locations, government regulations or limited space to manoeuver at the customer’s site, only a single truck may be needed to serve a few destinations and/or customers. These constraints are obvious in many practical situations [9–11]. Several researchers have so far contributed in this area. One instance is that of Gerdessen’s work on VRP with a trailer in 1996 . He demonstrated two real applications pertaining to TTRP. In one case it was the distribution of dairy products in cities where the distributor faced heavy traffic. Due to the fact that maneuvering a complete vehicle (a truck with a trailer) was difficult in some areas, and that some streets had traffic restrictions not allowing trailers to enter, the trailers were often parked in parking spots from which customers were serviced. The second case was the distribution of animal feed components to farmers. Because most villages have narrow roads or small bridges, different kinds of vehicles were required to deliver the feed to farmers, one of which was called a double bottom, consisting of a truck and a trailer. While the truck made deliveries using subtours (some parts of the tour) the trailer parked in a parking area. Gerdessen showed the necessity of considering TTRP by demonstrating real applications.In practical situations, a dispatcher may not know the exact demands in advance. Therefore, the company may face the problem of delivering products to customers with random demands. Consequently, unexpected extra costs might be imposed on the company. These issues can be considered in vehicle routing problems with stochastic demands (VRPSD). Moreover, when facing the limitations and restrictions mentioned above, VRPSD cannot cover these issues and needs to consider TTRP with stochastic demands (TTRPSD). The literature survey revealed no TTRP solution with stochastic parameters. Few articles were published on TTRP with deterministic parameters. However, papers published on stochastic VRP are simply large in number. These concepts need to be considered together in order to formulate TTRPSD. Therefore, this paper classifies the relevant papers into two groups—standard TTRP papers and VRP with stochastic demands. To solve TTRPSD, it appears that its solution is computationally more difficult than VRPSD. Indeed, VRP itself is one of the most difficult combinatorial optimization modelling problems. It is generally frame