پرتفوی های الگوریتم برای بهینه سازی لجستیک با توجه به تقاضاهای تصادفی و حد مجاز جا به جایی

The vehicle routing problem with stochastic demand (VRPSD) is a well known NP-hard problem. The uncharacteristic behaviour associated with the problem enhances the computational efforts required to obtain a feasible and near-optimal solution. This paper proposes an algorithm portfolio methodology based on evolutionary algorithms, which takes into account the stochastic nature of customer demand to solve this computationally complex problem. These problems are well known to have computationally complex objective functions, which make their solutions hard to find, particularly when problem instances of large dimensions are considered. Of particular importance in such situations is the timeliness of the solution. For example, Apple was forced to delay their shipments of iPads internationally due to unprecedented demand and issues with their delivery systems in Samsung Electronics and Seiko Epson. Such examples illustrate the importance of stochastic customer demands and the timing of delivery. Moreover, most of the evolutionary algorithms, known for providing computationally efficient solutions, are unable to always provide optimal or near optimal solutions to all the VRPSD instances within allocated time interval. This is due to the characteristic variations in the computational time taken by evolutionary algorithms for same or varying size of the VRPSD instances. Therefore, this paper presents portfolios of different evolutionary algorithms to reduce the computational time taken to resolve the VRPSD. Moreover, an innovative concept of the mobility allowance (MA) in landmoves based on the levy’s distribution function has been introduced to cope with real situations existing in vehicle routing problems. The proposed portfolio approach has been evaluated for the varying instances of the VRPSD. Four of the existing metaheuristics including Genetic Algorithm (GA), Simulated Annealing (SA), Artificial Immune System (AIS), TABU Search (TS) along with new neighbourhood search, are incorporated in the portfolios. Experiments have been performed on varying dimensions of the VRPSD instances to validate the different properties of the algorithm portfolio. An illustrative example is presented to show that the set of metaheuristics allocated to certain number of processors (i.e. algorithm portfolio) performed better than their individual metaheuristics.

There are several NP hard problems in the areas of graph theory, scheduling and coding theory for which a computationally efficient solution has not been found or shown to be non-existent (Stinson, 1987). This uncharacteristic behaviour is due to the stochastic nature of problem, its size and complexity. Further, the nonlinear characteristics of the objective function of NP hard problems also contribute to an increase in computational complexity. Common examples of non-deterministic engineering problems with uncertainties include vehicle routing problems with stochastic demands (VRPSDs) (Moghaddama et al., 2012, Goodson et al., 2012 and Yang et al., 2000), inventory routing problems (Shukla et al., 2012 and Agghezzaf et al., 2006), travelling salesman problem (TSP) of varying size (De Berg, 2005), and lot-sizing problems with stochastic demands (Raa, 2005). This paper focuses on developing a decision support methodology for resolving varying instances of the VRPSD problem in a computationally efficient way. Next, we briefly discuss the VRPSDs followed by the need for algorithm portfolios and relevant literature. The Vehicle Routing Problem (VRP) deals with the transportation of goods and services between geographically dispersed cities or customer locations by means of a fleet of vehicles. Solution to such a problem means determining the best set of possible vehicle routes, servicing all customers and optimising related constraints such as vehicles capacity, time windows, driver’s maximum working time, etc. VRPs are of major focus in supply-chain systems today, and they are becoming increasingly complex and challenging. For this reason, it has attracted various researchers to develop routing models that are more dynamic, stochastic, and incorporate all constraints, thereby enhancing the computational complexity associated with the objective function. Although several VRPSD models exist, they mainly consider the routing of the vehicle to be a flat path that ensures smooth movement of the vehicles. Based on the general performance and design of vehicles, approximate velocity is assigned to these vehicles. The assumption of smooth flow of vehicles may be useful in some but not necessairly all cases. Usually, ground movement of vehicles is hampered by areas of uneven terrain, which diminishes the effective movement of the vehicle (or the distance traversed is increased). Therefore, the distance traveled by vehicles must be approximated in close range with a view to use some distribution function that is able to fully map the variations originated due to uneven paths. This paper models such variations using the concept of mobility allowance that views the land disruptions as an extra distance that the vehicles have to cover. In this paper, levy's distribution function has been used to model various types of land disruptions. The theoretical base of this approach bridges the existing research gap and brings closer a practical solution to VRPSDs by considering and modelling issues of mobility allowance. It is widely recognized that the VRP is one of the most challenging problems to solve (Lim and Wang, 2005). Conceptually, VRP is an NP hard problem that can be viewed as the combination of the Travelling Salesman Problem (TSP) and the Bin Packing Problem (BPP). It is believed that one may never find a computational technique that will guarantee optimal solutions to larger instances for such problems. Even for small fleet sizes and a moderate number of transportation requests, the planning task is highly complex. The optimal strategies do find their application in resolving academic problems of insignificant dimensions, but the real world problem demands more robust heuristic and metaheuristic approaches to solve such problems in the required time frame. The increasing use of the metaheuristics has dramatically reduced the time taken to resolve these problems without much depreciation in the solution quality. The main contributions of this study are as follows: • This research introduces the concept of mobility allowance in vehicle routes to mathematically formulate the terrain uncertainties using the Levy distribution function. Thus providing more logical and mathematical grounds for encountering discrepancies in land moves. A mathematical model for estimating the extra distance traversed by vehicles has been also presented to incorporate the complexities. • This research provides the mechanism for employing key metaheuristics running on multiple processors for providing effective and efficient solutions than the individually running algorithms. • The proposed method is a more reliable and efficient decision support methodology in terms of producing quick and reliable solutions for complex and dynamically changing instances of VRPSDs. It takes the advantage of combining metaheuristic search approaches with several processors to arrive at the best solution in minimum computational time. Therefore, this research extends the existing literature in vehicle routing by providing a strong and useful alternative to tradiational VRP solutions. Further, this paper also provides mechanisms for algorithm portfolio design, mathematical and statistical evaluation, and analysis for the vehicle routhing problems with stochastic demands and mobility allowance. The rest of the paper is organized as follows: Section 2 discusses literature review and identifies current reserch gaps. Section 3 presents mathematical modeling of Stochastic Vehicle Routing Problem (SVRP). Section 4 gives a detailed modeling and approximation on the mobility allowance for the vehicle routings. Section 5 describes the concept of algorithm portfolios, details the implementation of the four basic metaheuristics and their advanced variants with the new neighborhood generators, and explains the experimental background used in this paper. Section 6 details the wider insights of the study to the comparative performance of the metaheuristics, and analyzes the functioning of the portfolios along with suggestions to optimal soultuions. Finally, Section 7 concludes the paper with some discussion on future research directions.

There are several NP hard problems in the areas of graph theory, scheduling and coding theory for which a computationally efficient solution has not been found or shown to be non-existent (Stinson, 1987). This uncharacteristic behaviour is due to the stochastic nature of problem, its size and complexity. Further, the nonlinear characteristics of the objective function of NP hard problems also contribute to an increase in computational complexity. Common examples of non-deterministic engineering problems with uncertainties include vehicle routing problems with stochastic demands (VRPSDs) (Moghaddama et al., 2012, Goodson et al., 2012 and Yang et al., 2000), inventory routing problems (Shukla et al., 2012 and Agghezzaf et al., 2006), travelling salesman problem (TSP) of varying size (De Berg, 2005), and lot-sizing problems with stochastic demands (Raa, 2005). This paper focuses on developing a decision support methodology for resolving varying instances of the VRPSD problem in a computationally efficient way. Next, we briefly discuss the VRPSDs followed by the need for algorithm portfolios and relevant literature. The Vehicle Routing Problem (VRP) deals with the transportation of goods and services between geographically dispersed cities or customer locations by means of a fleet of vehicles. Solution to such a problem means determining the best set of possible vehicle routes, servicing all customers and optimising related constraints such as vehicles capacity, time windows, driver’s maximum working time, etc. VRPs are of major focus in supply-chain systems today, and they are becoming increasingly complex and challenging. For this reason, it has attracted various researchers to develop routing models that are more dynamic, stochastic, and incorporate all constraints, thereby enhancing the computational complexity associated with the objective function. Although several VRPSD models exist, they mainly consider the routing of the vehicle to be a flat path that ensures smooth movement of the vehicles. Based on the general performance and design of vehicles, approximate velocity is assigned to these vehicles. The assumption of smooth flow of vehicles may be useful in some but not necessairly all cases. Usually, ground movement of vehicles is hampered by areas of uneven terrain, which diminishes the effective movement of the vehicle (or the distance traversed is increased). Therefore, the distance traveled by vehicles must be approximated in close range with a view to use some distribution function that is able to fully map the variations originated due to uneven paths. This paper models such variations using the concept of mobility allowance that views the land disruptions as an extra distance that the vehicles have to cover. In this paper, levy's distribution function has been used to model various types of land disruptions. The theoretical base of this approach bridges the existing research gap and brings closer a practical solution to VRPSDs by considering and modelling issues of mobility allowance. It is widely recognized that the VRP is one of the most challenging problems to solve (Lim and Wang, 2005). Conceptually, VRP is an NP hard problem that can be viewed as the combination of the Travelling Salesman Problem (TSP) and the Bin Packing Problem (BPP). It is believed that one may never find a computational technique that will guarantee optimal solutions to larger instances for such problems. Even for small fleet sizes and a moderate number of transportation requests, the planning task is highly complex. The optimal strategies do find their application in resolving academic problems of insignificant dimensions, but the real world problem demands more robust heuristic and metaheuristic approaches to solve such problems in the required time frame. The increasing use of the metaheuristics has dramatically reduced the time taken to resolve these problems without much depreciation in the solution quality. The main contributions of this study are as follows: • This research introduces the concept of mobility allowance in vehicle routes to mathematically formulate the terrain uncertainties using the Levy distribution function. Thus providing more logical and mathematical grounds for encountering discrepancies in land moves. A mathematical model for estimating the extra distance traversed by vehicles has been also presented to incorporate the complexities. • This research provides the mechanism for employing key metaheuristics running on multiple processors for providing effective and efficient solutions than the individually running algorithms. • The proposed method is a more reliable and efficient decision support methodology in terms of producing quick and reliable solutions for complex and dynamically changing instances of VRPSDs. It takes the advantage of combining metaheuristic search approaches with several processors to arrive at the best solution in minimum computational time. Therefore, this research extends the existing literature in vehicle routing by providing a strong and useful alternative to tradiational VRP solutions. Further, this paper also provides mechanisms for algorithm portfolio design, mathematical and statistical evaluation, and analysis for the vehicle routhing problems with stochastic demands and mobility allowance. The rest of the paper is organized as follows: Section 2 discusses literature review and identifies current reserch gaps. Section 3 presents mathematical modeling of Stochastic Vehicle Routing Problem (SVRP). Section 4 gives a detailed modeling and approximation on the mobility allowance for the vehicle routings. Section 5 describes the concept of algorithm portfolios, details the implementation of the four basic metaheuristics and their advanced variants with the new neighborhood generators, and explains the experimental background used in this paper. Section 6 details the wider insights of the study to the comparative performance of the metaheuristics, and analyzes the functioning of the portfolios along with suggestions to optimal soultuions. Finally, Section 7 concludes the paper with some discussion on future research directions.