This study presents a variant of Vehicle Routing Problem with Time Windows (VRPTW) by considering the delivery process of perishable products. The quality and quantity of perishable products are critical when they decay while in transit. Due to this property- the product freshness as a function of time, each vehicle must finish the delivery process to ensure that products are still in good condition. The problem is called the Vehicle Routing Problem with Time Windows for Perishable Products (VRPTWPP). The objective of VRPTWPP is to find a set of delivery routes to serve customers with known geographical locations and demands while minimizing total travel cost under time window restrictions, product shelf-life, and loading and unloading service time restrictions at customer sites.
A mixed integer programming model is formulated for the problem and a Simulated Annealing (SA) heuristic is developed to solve the proposed model. The proposed SA algorithm is tested on small and large size VRPTWPP instances adapted from well-known VRPTW benchmark data. Results shows that the proposed SA algorithm efficiently and effectively solves the VRPTWPP.

This study presents a variant of Vehicle Routing Problem with Time Windows (VRPTW) by considering the delivery process of perishable products. The quality and quantity of perishable products are critical when they decay while in transit. Due to this property- the product freshness as a function of time, each vehicle must finish the delivery process to ensure that products are still in good condition. The problem is called the Vehicle Routing Problem with Time Windows for Perishable Products (VRPTWPP). The objective of VRPTWPP is to find a set of delivery routes to serve customers with known geographical locations and demands while minimizing total travel cost under time window restrictions, product shelf-life, and loading and unloading service time restrictions at customer sites.
A mixed integer programming model is formulated for the problem and a Simulated Annealing (SA) heuristic is developed to solve the proposed model. The proposed SA algorithm is tested on small and large size VRPTWPP instances adapted from well-known VRPTW benchmark data. Results shows that the proposed SA algorithm efficiently and effectively solves the VRPTWPP.

Aarts, E., & Korst, J. (1989). Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. John Wiley & Sons, Chichester, England.
Aarts, E., & Lenstra, J. K. (1997). Local Search in Combinatorial Optimization: John Wiley & Sons, Inc. New York, NY, USA
Alvarengaa, G. B., Mateus, G. R., & Tomi, G. d. (2007). A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. computers & operations research, 34, 1561-1584.
Amorim, P., & Almada-Lobo, B. (2014). The impact of food perishability issues in the vehicle routing problem. Computers & Industrial Engineering, 67, 223-233.
Bent, R., & Hentenryck, P. V. (2004). A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows. Transportation Science, 38(4), 515-530.
Berger, J., & Barkaoui, M. (2004). A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & operations research, 31, 2037-2053.
Berger, J., Barkaoui, M., & Bräysy, O. (2003). A Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows. Information Systems and Operational Research, 41, 179-194.
Bonomi, E., & Lutton, J. L. (1986). The asymptotic behavior of quadratic sum assignment problems: A statistical mechanics approach. European Journal of Operational Research, 26, 295-300.
Bräysy, O., & Gendreau, M. (2005). Vehicle Routing Problem with Time Windows, Part II: Metaheuristics. Transportation Science, 39(1), 119-139.
Cerny, V. (1985). Thermodynamic approach to the traveling salesman problem. Journal of optimization theory and applications, 45, 41-51.
Czech, Z. J., & Czarnas, P. (2002). A Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows. 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands–Spain.
Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (1954). Solution of a large-scale travelling-salesman problem. Operations Research Society of America, 393-410.
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6, 80-91.
Desaulniers, G., Madsen, O. B. G., & Ropke, S. (2002). The vehicle routing problem with time windows Vehicle Routing problems, methods, and applications. (pp. 119-159). Philadelphia: The Mathematical Optimization Society and the Society for Industrial and Applied Mathematics.
Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. 40, 342-354.
Eglese, R. W. (1990). Simulated annealing: a tool for operational research. European Journal of Operational Research, 46, 271-281.
Eksioglu, B., Vural, A. V., & Reisman, A. (2009). The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57, 1472-1483.
Fisher, M. L., Jornsten, K. O., & Madsen, O. B. G. (1997). Vehicle routing with time windows – two optimization algorithms. Operations Research, 45(3), 488-498.
Fleischer, M. (1995). Simulated annealing: past, present, and future. Proceedings of the 1995 Winter Simulation Conference, ed. C. Alexopoulos, K. Kang, W. R. Lilegdon, and D. Goldsman.
Friesz, T., Cho, H. J., Mehta, N., Tobin, R., & Anandalingam, G. (1992). A simulated annealing approach to the network design problem with variational inequality constraints. Transportation Science, 26, 18-26.
Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. New Ideas in Optimization.
Gendreau, M., Potvin, J.-Y., Bräumlaysy, O., Hasle, G., & Lkketangen, A. (2008). Metaheuristics for the Vehicle Routing Problem and Its Extensions: A Categorized Bibliography. In B. Golden, S. Raghavan & E. Wasil (Eds.), The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces. Vol. 43. (pp. 143-169): Springer US.
Golden, B. L., Magnanti, T. L., & Nguyen, H. Q. (1977). Implementing vehicle routing algorithms. Networks, 7(2), 113-148.
Halse, K. (1992). Modeling and solving complex vehicle routing problems. The Technical University of denmark, Lyngby, Denmark
Henderson, D., Jacobson, S. H., & Johnson, A. W. (2003). The theory and practice of simulated annealing. In G. A. K. F. Glover (Ed.), Handbook of metaheuristics. Newyork, Boston, Dordrecht, London, Moscow: Kluwer Academic publishers.
Homberger, J. (2000). Verteilt-parallele Metaheuristiken zur Tourenplanung: Deutscher Universitätsverlag.
Homberger, J., & Gehring, H. (1999). Two Evolutionary Metaheuristics for the Vehicle Routing Problem with Time Windows. INFOR 37, 297-318.
Hsu, C. I., Hung, S. F., & Li, H. C. (2007). Vehicle routing problem with time-windows for perishable food delivery. Journal of Food Engineering 80, 465-475.
Ibaraki, T., Kubo, M., Masuda, T., Uno, T., & Yagiura, M. (2001). Effective Local Search Algorithms for the Vehicle Routing Problem with General Time Windows. 4th Metaheuristics International Conference.
Kallehauge, B., Larsen, J., Madsen, O. B. G., & Solomon, M. M. (2005). Vehicle routing problem with time windows. In G. Desaulniers, J. Desrosiers & M. M. Solomon (Eds.), Column Generation. (pp. 67-98): Springer US.
Kohl, N., Desrosiers, J., Madsen, O. B. G., Solomon, M. M., & Soumis, F. (1999). 2-Path Cuts for the Vehicle Routing Problem with Time Windows. Transportation Science, 33(1), 101-116.
Koulamas, C., Antony, S. R., & Jaen, R. (1994). A survey of simulated annealing applications to operations-research problems. OMEGA-International Journal of Management Science, 22, 41-56.
Laporte, G. (1992). The Vehicle Routing Problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59, 345-358.
Lenstra, J., & Rinnooy, K. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11, 221–227.
Li, H., & Lim, A. (2003). Local search with annealing-like restarts to solve the VRPTW. European Journal of Operational Research, 150, 115-127.
Lin, C., Choy, K. L., Ho, G. T. S., Chung, S. H., & Lam, H. Y. (2014). Survey of Green Vehicle Routing Problem: Past and future trends. Expert Systems with Applications, 41, 1118-1138.
Matsuo, H., Suh, C., & Sullivan, R. (1987). A controlled search simulated annealing method for the general job shop scheduling problem, Working paper. Graduate School of Business, University of Texas at Austin.
Mester, D., Braysy, O., & Dullaert, W. (2007). A multi-parametric evolution strategies algorithm for vehicle routing problems. Expert Systems with Applications, 32, 507-517.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., & Teller, A. H. (1953). Equation of State Calculations by Fast Computing Machines. The journal of chemical physics, 21, 1087–1091.
Osvald, A., & Stirn, L. Z. (2008). A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food. Journal of Food Engineering, 85, 285-295.
Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & operations research, 34(8), 2403-2435.
Rochat, Y., & Taillard, E. D. (1995). Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics, 1, 147-167.
Romeo, F., & Sangiovanni-Vincentelli, A. (1991). A theoretical framework for simulated annealing. Algorithmica, 6, 302-345.
Rousseau, L. M., Gendreau, M., & Pesant, G. (2002). Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows. Journal of Heuristics, 8, 43-58.
Schmid, V., Doerner, K. F., Hartl, R. F., Savelsbergh, M. W. P., & Stoecher, W. (2009). A Hybrid Solution Approach for Ready-Mixed Concrete Delivery. Transportation Science, 43(1), 70-85.
Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H., & Dueck, G. (2000). Record Breaking Optimization Results Using the Ruin and Recreate Principle. Journal of Computational Physics, 159(2), 139-171.
Shaw, P. (1997). A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems. APES Group; Department of Computer Science,; University of Strathclyde,.
Shaw, P. (1999). Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems Principles and Practice of Constraint Programming — CP98. Lecture Notes in Computer Science. Vol. 1520. (pp. 417-431).
Solomon, M. M. (1983). Vehicle routing and scheduling with time windows constraints: models and algorithms. University of Pennsylvania, USA.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time windows constraints. Operations Research Society of America, 35(2), 254–265.
Song, B. D., & Ko, Y. D. (2016). A vehicle routing problem of both refrigerated- and general-type vehicles for perishable food products delivery. Journal of Food Engineering, 169, 61-71.
Taillard, É., Badeau, P., Gendreau, M., Guertin, F., & Potvin, J.-Y. (1997). A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Transportation Science, 31(2), 170-186.
Tarantilis, C. D., & Kiranoudis, C. T. (2001). A meta-heuristic algorithm for the efficient distribution of perishable foods. Journal of Food Engineering, 50, 1-9.
Tarantilis, C. D., & Kiranoudis, C. T. (2002). Distribution of fresh meat. Journal of Food Engineering, 51, 85-91.
Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. Philadelphia: The Mathematical Optimization Society and the Society for Industrial and Applied Mathematics.
van Laarhoven, P. J. M., & Aarts, E. H. L. (1987). Simulated Annealing: Theory and Applications. D. Reidel Publishing Company, Dordrecht, Holland: Springer Science+Business Media Dordrecht
Wilhelm, M. R., & Ward, T. L. (1987). Solving quadratic assignment problems by simulated annealing. IEEE Transactions, 19, 107-119.
Woch, M., & Łebkowski, P. (2009). Sequential Simulated Annealing for the Vehicle Routing Problem with Time Windows. Decision Making in Manufacturing and Services. Decision Making in Manufacturing and Services, 3(1-2), 87-100.