Abstract

The real-time vehicle routing problem with time windows and simultaneous delivery products and pickup wastage materials (RT-VRPTWDPPWM) is formulated as extension of VRP. The real-time delivery/pickup demands are served by capacitated vehicles with limited initial loads. Moreover, pickup services aren't necessarily done after delivery services in each route. A improved genetic algorithm ( master-slave genetic algorithm)is proposed. To generate offspring for the next generation for crossover (Sub Route Sequence Crossover Method (SRSCM) and for mutation (Sub Route Alter Mutation Method (SRAMM) methods are introduced. The results shows that the proposed algorithm can efficiently decrease the total route cost. Results of comparative tests are presented showing that the improved algorithm performs well on large populations.

References

• Paredis, J. 1998. The handbook of evolutionary computation. Oxford University Press, Chap. Coevolutionary Algorithms.
• DeJong, K. and Potter, M. 1995. Evolving Complex Structures via Cooperative Coevolution Evolutionary Programming, MIT Press Journal, pp. 307-317.
• Dhaenens, C. , Lemesre, J. and Talbi, E. 2009. A new exact method to solve multi-objective combinatorial optimization problems. European Journal of Operational Research, vol. 200, No. 1, pp. 45-53.
• Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability, A Guide to The Theory of NP-Completeness. New York: W. H. Freeman and Company, 1979.
• Chand, P. and Mohanty, J. R. 2011. Multi Objective GeneticApproach for Solving Vehicle Routing Problem with Time Window. In Proceedings of the CCSEIT Conference on Computer Science Engineering and InformationTechnology, IEEE Press, Sep. 2011,vol. 204, pp. 336-343.
• Ombuki, B. , Ross, J. , Brian, J. and Hanshar, F. 2006. Multi Objective Genetic Algorithms for Vehicle Routing Problems with Time Windows. IEEE Journal of Applied Intelligence, vol. 24, pp. 17-30.
• Deb, K. 2001. Multi- Objective Optimization Using Evolutionary Algorithm. Chichester, UK: John Wiley & Sons, Ltd.
• Goldberg 2007. Genetic Algorithms in Search,Optimization, and Machine Learning , Addison-Wesley.
• Chand, P. and Mohanty,J. R. 2013. A Multi-objective Vehicle Routing Problem using Dominant Rank Method. International Journal of Computer Application, pp. 29-34.
• Lohn, J. , Kraus, W. and Haith, G. 2002. Comparing a Coevolutionary Genetic Algorithm for Multiobjective Optimization. In Proceedings of the IEEE Congress on Evolutionary Computation, pp. 1157-1162.
• Cvetkovic, D. and Parmee, I. C. 1999. Genetic algorithm-based multi-objective optimisation and conceptual engineering design. In Proceedings of the CEC Conference on Evolutionary Computation, vol. 1.
• Stanley, K. O. and Miikkulainen, R. 2006. Evolving Neural Networks through Augmenting Topologies. Journal of Evolutionary Computation, vol. 10, No. 2, pp. 99-127
• Venkadesh, S. , Hoogenboom, G. , Potter, W. and McClendon, R. 2013. A genetic algorithm to refine input data selection for air temperature prediction using artificial neural networks. Journal of Applied Soft Computing, vol. 13, No. 5, pp. 2253-2260.
• Devert, A. Weise, T. and Tang, K. 2012. A Study on Scalable Representations for Evolutionary Optimization of Ground Structures. Journal of Evolutionary Computation, vol. 20, No. 3, pp. 453-472.
• Chandra, A. and Yao, X. 2006. Ensemble Learning Using Multi-Objective Evolutionary Algorithms. Journal of Mathematical Modelling and Algorithms, vol. 5, No. 4, pp. 417-445.
• Konaka, A. , Coitb, D. W. and Smith, A. E. 2006. Multi-objective optimization using genetic algorithms. A tutorial, Reliability Engineering and System Safety, Elsevier Press, vol. 91, pp. 992-1007.
• Hajela, P. and lin, C. Y. 1992. Genetic search strategies in multicriterion optimal design, Struct Optimization. Journal of Engineering Optimisation, vol. 4, No. 2, pp. 99–107.
• Ropke, S. and Pisinger, D. 2006. A unified heuristic for a large class of Vehicle Routing Problems with Backhauls. European Journal of Operational Research , vol. 171, pp. 750–775.
• Bianchessi, N. and Righin,i G. 2007. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Journal of Computers & Operations Research, vol. 34, pp. 578–594.
• Baker, B. M. and Ayechew, M. A. 2003. Agenetic algorithm for the vehicle routing problem. Journal of Computers & Operations Research, vol. 30, pp. 787–800.
• Stock, J. R. 1992. Reverse Logistics. Council of Logistics Management, Oak Brook , IL.
• Min, H. 1989. The multiple vehicle routing problem with simultaneous delivery and pickup points. Journal of
• Transportation Research, vol. 23, pp. 377–386.
• Dethloff, J. "Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up". OR Spektrum. 23, pp. 79–96.
• Angelelli, E. and Mansini, R. 2003A branch-and-price algorithm for a simultaneous pick-up and delivery problem. Technical Report . EURO/INFORMS Meeting.
• Tang, F. A. and Galvao, R. D. 2002. Vehicle routing problems with simultaneous pick-up and delivery service. Journal of the Operational Research Society of India, vol. 39, pp. 19–33.
• Tang, F. A. and Galvao, R. D. 2006. A tabu search algorithm for the vehicle routing problems with simultaneous pick-up and delivery service. Journal of Computer & Operation Research, vol. 33, pp. 595-619.
• Baker, B. M. and Ayechew, M. A. 2003. A Genetic Algorithm for the Vehicle Routing Problem. Journal of Computers & Operations Research. Vol. 30, pp. 787-800.
• Christian, P. 2004. A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem. Journal of Computers & Operations Research, vol. 31, pp. 1985-2002.
• Gen, M. and Cheng, R. 2000. Genetic Algorithms &Engineering Optimization. New York: Wiley.
• Storn R. 1996. Differential evolution design of an IIR-filter. In Proceedings of the IEEE Conference on Evolutionary Computation, IEEE Press, pp. 268-273.
• Aiex, R. M. , Resende, M. G. C. and Ribeiro, C. C. 2002. Probability distribution of solution time in GRASP. An experimental investigation. Journal of Heuristics, vol. 8, pp. 343–373.
• Angelelli, E. and Mansini, R. Quantitative Approaches to Distribution Logistics and Supply Chain Management, chapter A branch-and-price algorithm for a simultaneous pick-up and delivery problem, Springer, pp. 249–267, 2002.
• Berbeglia, G. , Cordeau, J. F. , Gribkovskaia, I. and Laporte, G. Static pickup and delivery problems, A classification scheme and survey, vol. 15, pp. 1–31, 2007.
• Bianchessi, N. and Righini, G. 2007. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Journal of Computers & Operations Research, vol. 34, No. 2, pp. 578–594.
• Chen, J. F. 2006. Approaches for the vehicle routing problem with simultaneous deliveries and pickups. Journal of the Chinese Institute of Industrial Engineers, vol. 23, No. 2, pp. 141–150.
• Chen, J. F. and Wu, T. H. 2005. Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, vol. 57, No. 5, pp. 579–587.
• Crispim, J. and Brandao, J. 2005. Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls. Journal of the Operational Research Society, vol. 56, No. 7, pp. 1296–1302, 2005.
• Amico, M. D. , Righini, G. and Salanim, M. 2006. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Journal of Transportation Science, vol. 40, No. 2, pp. 235–247.
• Dethloff, J. 2001. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. Journal of OR Spectrum, vol. 23, pp. 79–96.
• Gribkovskaia, I. , Halskau, Q. , Laporte, G. and Vlcek, M. 2007. General solutions to the single vehicle routing problem with pickups and deliveries. European Journal of Operational Research, vol. 180, pp. 568– 584.
• Min, H. 1989. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Journal of Transportation Research, vol. 23, No. 5, pp. 377–386.
• Montane, F. A. T. and Galvao, R. D. 2006. A tabu search algorithm for the vehicle routing problem with simultaneouspick-up and delivery service. European Journal of Operational Research, vol. 33, No. 3, pp. 595–619.
• Nagy, G. and Salhi, S. 2005. Heuristic algorithms for single and multiple depot vehicle routing problems with pickupsand deliveries. European Journal of Operational Research, vol. 162, pp. 126–141.
• Wassan, N. A. , Wassan, A. H. and Nagy,G. A . 2008. reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries. Journal of Combinatorial Optimization, vol. 15, No. 4, pp. 368–386.