Transportation is the main component of supply chain cost; therefore, it is critical to overall logistics and supply chain success. One of the decisions in transportation planning is the vehicle routing decision (VRP). Studies on VRP are divided into two groups, namely, traditional VRP and green VRP (GVRP). In this study, we describe two variants of VRP, namely, capacitated green-VRP (CG-VRP) as a variant in GVRP and the location routing problem with time-dependent demand (LRPTDD) as a variant in traditional VRP.
CG-VRP is an extension of the green-VRP (G-VRP) that considers the use of alternative fuel such that we called it the alternative fuel vehicle (AFV). The mathematical model of CG-VRP is formulated as a mixed-integer linear program (MILP) to minimize the total distance traveled by an AFV. Meanwhile, LRPTDD is an extension of the location routing problem (LRP) by considering the demand flowing at a constant rate over a known production period associated with each customer; therefore, the amount of demand will depend on the time. We formulate a mathematical model of LRPTDD as a mixed-integer nonlinear programming (MINLP) to minimize the total cost comprised of routing cost, depot cost, and vehicle utility cost. We develop a simulated annealing algorithm for the solution approach corresponding to each problem.
The computational study demonstrates the competitiveness of the proposed simulated annealing (SA) compared to other well-known algorithms used for both G-VRP and LRP benchmark instances. The result shows that the proposed SA performs well in both CG-VRP and LRPTDD. The proposed model can obtain a good solution at a reasonable time for both problems.

Transportation is the main component of supply chain cost; therefore, it is critical to overall logistics and supply chain success. One of the decisions in transportation planning is the vehicle routing decision (VRP). Studies on VRP are divided into two groups, namely, traditional VRP and green VRP (GVRP). In this study, we describe two variants of VRP, namely, capacitated green-VRP (CG-VRP) as a variant in GVRP and the location routing problem with time-dependent demand (LRPTDD) as a variant in traditional VRP.
CG-VRP is an extension of the green-VRP (G-VRP) that considers the use of alternative fuel such that we called it the alternative fuel vehicle (AFV). The mathematical model of CG-VRP is formulated as a mixed-integer linear program (MILP) to minimize the total distance traveled by an AFV. Meanwhile, LRPTDD is an extension of the location routing problem (LRP) by considering the demand flowing at a constant rate over a known production period associated with each customer; therefore, the amount of demand will depend on the time. We formulate a mathematical model of LRPTDD as a mixed-integer nonlinear programming (MINLP) to minimize the total cost comprised of routing cost, depot cost, and vehicle utility cost. We develop a simulated annealing algorithm for the solution approach corresponding to each problem.
The computational study demonstrates the competitiveness of the proposed simulated annealing (SA) compared to other well-known algorithms used for both G-VRP and LRP benchmark instances. The result shows that the proposed SA performs well in both CG-VRP and LRPTDD. The proposed model can obtain a good solution at a reasonable time for both problems.

REFERENCES
Afshar-Nadjafi, B., & Afshar-Nadjafi, A. (2016). Multi-depot time dependent vehicle routing problem with heterogeneous fleet and time windows. International Journal of Operational Research, 26(1), 88-103.
Ai, T. J., & Kachitvichyanukul, V. (2009). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 56(1), 380-387.
Albareda-Sambola, M., Dı́az, J. A., & Fernández, E. (2005). A compact model and tight bounds for a combined location-routing problem. Computers & Operations Research, 32(3), 407-428.
Baker, B. M., & Ayechew, M. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.
Baldacci, R., Mingozzi, A., & Wolfler Calvo, R. (2011). An exact method for the capacitated location-routing problem. Operations Research, 59(5), 1284-1296.
Bard, J. F., Huang, L., Dror, M., & Jaillet, P. (1998). A branch and cut algorithm for the VRP with satellite facilities. IIE transactions, 30(9), 821-834.
Barreto, S. (2004). Analysis and modeling of location-routing problems. Portugal: University of Aveiro.
Barreto, S., Ferreira, C., Paixao, J., & Santos, B. S. (2007). Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, 179(3), 968-977.
Beamon, B. M. (1998). Supply chain design and analysis: Models and methods. International Journal of Production Economics, 55(3), 281-294.
Belenguer, J.-M., Benavent, E., Prins, C., Prodhon, C., & Calvo, R. W. (2011). A branch-and-cut method for the capacitated location-routing problem. Computers & Operations Research, 38(6), 931-941.
Bjorklund, M. (2011). Influence from the business environment on environmental purchasing — Drivers and hinders of purchasing green transportation services. Journal of Purchasing & Supply Management, 17, 11–22.
Bouhafs, L., & Koukam, A. (2006). A combination of simulated annealing and ant colony system for the capacitated location-routing problem. Proceedings of the Knowledge-Based Intelligent Information and Engineering Systems (pp. 409-416).
Boventer, E. (1961). The relationship between transportation costs and location rent in transportation problems. Journal of Regional Science, 3(2), 27-40.
Bräysy, O. (2003). A reactive variable neighborhood search for the vehicle-routing problem with time windows. INFORMS Journal on Computing, 15(4), 347-368.
Bree, B. v., Verbong, G. P. J., & Krame, G. J. (2010). A multi-level perspective on the introduction of hydrogen and battery-electric vehicles. Technological Forecasting & Social Change, 77, 529–540.
Breedan, A. V. (1995). Improvement heuristic for the Vehicle Routing Problem based on Simulated Annealing. European Journal of Operation Research, 86, 480-490.
Campbell, A. R., Ryley, T., & Thring, R. (2012). Identifying the early adopters of alternative fuel vehicles: A case study of Birmingham, United Kingdom. Transportation Research Part A, 46, 1318–1327.
Chen, H.-K., Hsueh, C.-F., & Chang, M.-S. (2006). The real-time time-dependent vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 42(5), 383-408.
Chien, T. W. (1993). Heuristic Procedures for Practical‐Sized Uncapacitated Location‐Capacitated Routing Problems. Decision Sciences, 24(5), 995-1021.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581.
Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., & Semet, F. (2002). A Guide to Vehicle Routing Heuristics. The Journal of the Operational Research Society, 53, 512-522.
Coy, S. P., Golden, B. L., Runger, G. C., & Wasil, E. A. (2001). Using experimental design to find effective parameter settings for heuristics. Journal of Heuristics, 7(1), 77-97.
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6, 80-91.
Demir, E., Huckle, K., Syntetos, A., Lahy, A., & Wilson, M. (2019). Vehicle Routing Problem: Past and Future Contemporary Operations and Logistics. (pp. 97-117): Springer.
Donati, A. V., Montemanni, R., Casagrande, N., Rizzoli, A. E., & Gambardella, L. M. (2008). Time dependent vehicle routing problem with a multi ant colony system. European journal of operational research, 185(3), 1174-1191.
Drexl, M., & Schneider, M. (2015). A survey of variants and extensions of the location-routing problem. European Journal of Operational Research, 241(2), 283-308.
Duhamel, C., Lacomme, P., Prins, C., & Prodhon, C. (2008). A memetic approach for the capacitated location routing problem. Proceedings of the EU/meeting 2008 workshop on metaheuristics for logistics and vehicle routing. University of Technology of Troyes, France.
Duhamel, C., Lacomme, P., Prins, C., & Prodhon, C. (2010). A GRASP× ELS approach for the capacitated location-routing problem. Computers & Operations Research, 37(11), 1912-1923.
Dukkanci, O., Kara, B. Y., & Bektaş, T. (2019). The green location-routing problem. Computers & Operations Research, 105, 187-202.
Erdogan, S., & Miller-Hooks, E. (2012). A Green Vehicle Routing Problem. Transportation Research Part E 48, 100-1014.
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations research, 22(2), 340-349.
Gmira, M., Gendreau, M., Lodi, A., & Potvin, J.-Y. (2019). Managing in Real-Time a Vehicle Routing Plan with Time-Dependent Travel Times on a Road Network.
Graham-Rowea, E., Gardner, B., Abrahamc, C., Skippond, S., Dittmar, H., Hutchins, R. et al. (2012). Mainstream consumers driving plug-in battery-electric and plug-in hybrid electric cars: a qualitative analysis of responses and evaluations. Transportation Research Part A, 46(1), 140–153.
Guo, R., & Tang, Q. (2008). An optimized supply chain planning model for manufacture company based on JIT. International Journal of Business and Management, 3(11), 129-133.
Gupta, A., & Maranas, C. D. (2003). Managing demand uncertainty in supply chain planning. Computers & chemical engineering, 27(8-9), 1219-1227.
Hashimoto, H., Yagiura, M., & Ibaraki, T. (2008). An iterated local search algorithm for the time-dependent vehicle routing problem with time windows. Discrete Optimization, 5(2), 434-456.
Jaballah, R., Veenstra, M., Coelho, L. C., & Renaud, J. (2019). The Time-dependent Shortest Path and Vehicle Routing Problem: CIRRELT, Centre interuniversitaire de recherche sur les réseaux d'entreprise ….
Kara, I., Kara, B. Y., & Yetis, M. K. (2007). Energy Minimizing Vehicle Routing Problem. Proceedings of the The 1st International Conference on Combinatorial Optimization and Applications (COCOA 2007) (pp. 58-67). Xi'an, China.
Karaoglan, I., & Altiparmak, F. (2010). A hybrid genetic algorithm for the location-routing problem with simultaneous pickup and delivery. Proceedings of the Computers and Industrial Engineering (CIE), 2010 40th International Conference on (pp. 1-6).
Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4), 465-477.
Khodakaram Salimifard, H. S. a. R. R. (2012). Green Transportation and the Role of Operation Research. 2012 International Conference on Traffic and Transportation Engineering (ICTTE 2012).
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simmulated annealing. Science, 220(4598), 671-680.
Koç, Ç., Bektaş, T., Jabali, O., & Laporte, G. (2016). The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm. European Journal of Operational Research, 248(1), 33-51.
Kuo, Y. (2010). Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering, 59, 157–165.
Laporte, G. (1992). The Vehicle Routing Problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 45–358.
Laporte, G., & Nobert, Y. (1981). An exact algorithm for minimizing routing and operating costs in depot location. European Journal of Operational Research, 6(2), 224-226.
Laporte, G., Nobert, Y., & Taillefer, S. (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science, 22(3), 161-172.
Lenstra, J. K., & Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227.
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.
Lin, C., & Kwok, R. (2006). Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data. European Journal of Operational Research, 175(3), 1833-1849.
Lin, S.-W., Ying, K.-C., and, Z.-J. L., & Hsi, F.-H. (2006). Applying Simulated Annealing Approach for Capacitated Vehicle Routing Problems. IEEE International Conference on Systems, Man, and Cybernetics, Taipei, Taiwan.
Lin, S.-W., Yu, V. F., & Lu, C.-C. (2011). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications, 38, 15244–15252.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516.
Liu, J., & Kachitvichyanukul, V. (2015). A particle swarm optimisation algorithm for the capacitated location-routing problem. International Journal of Operational Research, 24(2), 184-213.
Mazzeo, S., & Loiseau, I. (2004). An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Mathematics, 18, 181-186.
Min, H., & Kim, I. (2012). Green supply chain research: past, present, and future. Logist. Res., 4, 39–47.
Mole, R., & Jameson, S. (1976). A sequential route-building algorithm employing a generalised savings criterion. Journal of the Operational Research Society, 27(2), 503-511.
Nagata, Y., Bräysy, O., & Dullaert, W. (2010). A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers & operations research, 37(4), 724-737.
Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2), 649-672.
Nelson, M. D., Nygrad, K. E., Griffins, J. H., & Shreve, W. E. (1985). Implementation Techniques For The Vehicle Routing Problem. Compul. & Ops Res, 12(3), 273~.283.
Norouzi, N., Sadegh-Amalnick, M., & Tavakkoli-Moghaddam, R. (2016). Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption. Optimization Letters, 1-14.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of operations research, 41(4), 421-451.
Peidro, D., Mula, J., Poler, R., & Verdegay, J.-L. (2009). Fuzzy optimization for supply chain planning under supply, demand and process uncertainties. Fuzzy sets and systems, 160(18), 2640-2657.
Pop, P. C., Sitar, C. P., Zelina, I., Lupse, V., & Chira, C. (2011). Heuristic algorithms for solving the generalized vehicle routing problem. International Journal of Computers Communications & Control, 6(1), 158-165.
Prins, C., Prodhon, C., & Calvo, R. W. (2006a). A Memetic Algorithm with Population Management (MA| PM) for the Capacitated Location-Routing Problem. Lecture notes in computer science, 3906, 183-194.
Prins, C., Prodhon, C., & Calvo, R. W. (2006b). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR, 4(3), 221-238.
Prins, C., Prodhon, C., Ruiz, A., Soriano, P., & Wolfler Calvo, R. (2007). Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic. Transportation science, 41(4), 470-483.
Prins, C., Prodhon, C., & Wolfler-Calvo, R. (2004). Nouveaux algorithmes pour le problème de localisation et routage sous contraintes de capacité. Proceedings of the MOSIM (Vol. 4, pp. 1115-1122).
Prodhon, C., & Prins, C. (2014). A survey of recent research on location-routing problems. European Journal of Operational Research, 238(1), 1-17.
Redi, A. A. N. P., Maghfiroh, M. F., & Yu, V. F. (2013a). Discrete Particle Swarm Optimization with Path-Relinking for Solving the Open Vehicle Routing Problem with Time Windows. Proceedings of the Proceedings of the Institute of Industrial Engineers Asian Conference 2013 (pp. 853-859).
Redi, A. A. N. P., Maghfiroh, M. F., & Yu, V. F. (2013b). An improved variable neighborhood search for the open vehicle routing problem with time windows. Proceedings of the Industrial Engineering and Engineering Management (IEEM), 2013 IEEE International Conference on (pp. 1641-1645).
Rochat, Y., & Taillard, É. D. (1995). Probabilistic diversification and intensification in local search for vehicle routing. Journal of heuristics, 1(1), 147-167.
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4), 455-472.
Rosen, S. L., & Harmonosky, C. M. (2005). An improved simulated annealing simulation optimization method for discrete parameter stochastic systems. Computers & Operations Research, 32(2), 343-358.
Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39(2), 150-156.
Schneider, M., Stenger, A., & Goeke, D. (2014). The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations. Transportation Science, 140306073540008.
Soler, D., Albiach, J., & MartíNez, E. (2009). A way to optimally solve a time-dependent vehicle routing problem with time windows. Operations Research Letters, 37(1), 37-42.
Srivastava, R. (1993). Alternate solution procedures for the location-routing problem. Omega, 21(4), 497-506.
Stock, J. R., & Lambert, D. (2001). Strategic logistic management (fourth edition ed.). New York: Mc Graw Hill.
Sule, A. A., S, H. S., & Mingyuan, C. (1991). A 3-Opt Based Simulated Annealing Algorithm For Vehicle Routing Problems. Computers ind. Engng, 21(1-4), 635-663.
Sun, Y., Hrušovský, M., Zhang, C., & Lang, M. (2018a). A time-dependent fuzzy programming approach for the green multimodal routing problem with rail service capacity uncertainty and road traffic congestion. Complexity, 2018.
Sun, Y., Wang, D., Lang, M., & Zhou, X. (2018b). Solving the time-dependent multi-trip vehicle routing problem with time windows and an improved travel speed model by a hybrid solution algorithm. Cluster Computing, 1-12.
Ting, C.-J., & Chen, C.-H. (2013). A multiple ant colony optimization algorithm for the capacitated location routing problem. International Journal of Production Economics, 141(1), 34-44.
Toth, P., & Vigo, D. (2002). The vehicle routing problem. Philadelphia: SIAM monographs on discrete mathematics and applications.
Tuzun, D., & Burke, L. I. (1999). A two-phase tabu search approach to the location routing problem. European Journal of Operational Research, 116(1), 87-99.
Vincent, F. Y., & Lin, S.-Y. (2015). A simulated annealing heuristic for the open location-routing problem. Computers & Operations Research, 62, 184-196.
Wang, X., Sun, X., & Fang, Y. (2005). A two-phase hybrid heuristic search approach to the location-routing problem. Proceedings of the Systems, Man and Cybernetics, 2005 IEEE International Conference on (Vol. 4, pp. 3338-3343).
Waters, C. D. J. (1989). Vehicle-scheduling problems with uncertainty and omitted customers. The Journal of the Operational Research Society, 40, 1099–1108.
Wu, T.-H., Low, C., & Bai, J.-W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393-1415.
Xiao, Y., & Konak, A. (2016). The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transportation Research Part E: Logistics and Transportation Review, 88, 146-166.
Xiao, Y., Zhao, Q., Kaku, I., & Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers & Operations Research, 39(7), 1419-1431.
Yasin, M., & Yu, V. F. (2013). A Simulated Annealing Heuristic for the Green Vehicle Routing Problem (pp. 1261-1269).
Yu, V. F., Jewpanya, P., & Redi, A. A. N. P. (2016). Open vehicle routing problem with cross-docking. Computers & Industrial Engineering, 94, 6-17.
Yu, V. F., & Lin, S.-W. (2014). Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery. Applied Soft Computing, 24, 284-290.
Yu, V. F., Lin, S.-W., Lee, W., & Ting, C.-J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288-299.
Zarandi, M. H. F., Hemmati, A., Davari, S., & Turksen, I. B. (2013). Capacitated location-routing problem with time windows under uncertainty. Knowledge-Based Systems, 37, 480-489.
Zhang, S., Gajpal, Y., & Appadoo, S. (2017). A meta-heuristic for capacitated green vehicle routing problem. Annals of Operations Research, 1-19.