Facility location and vehicle routing problems are two critical decisions in designing a supply chain network. Although they are often solved separately because of the differences in their planning horizon, these two problems have been proven to be interdependent. Therefore, the location routing problem (LRP) is proposed to solve these problems simultaneously. The problem extend from a practical perspective when the companies do not have their own vehicles to deliver their products. Considering in some real-life situations, arrival time at a customer will affect the customer’s satisfaction level or sales to the customer. Each customer may have a specific service time window during which s/he can be serviced, and a service vehicle must arrive within this time window to start its service. Therefore, this study combines the open location routing problem (OLRP) and time windows constraint into the open location routing problem with time windows (OLRPTW). This study proposes a branch-and-price algorithm to solve OLRPTW. This problem is solved by the simplex algorithm in the master problem. The elementary shortest path problem with resource constraints (ESPPRC) is used in this pricing problem which has the goal to generate feasible routes with negative reduced costs to be added to the restricted master problem (RMP). The OLRPTW instances are derived from three LRP benchmark data sets. The computational result indicates that the branch-and-price algorithm is comparable for small-medium instances. For large instances, it can solve instance with 200 customers and 10 depots to the optimality.

Facility location and vehicle routing problems are two critical decisions in designing a supply chain network. Although they are often solved separately because of the differences in their planning horizon, these two problems have been proven to be interdependent. Therefore, the location routing problem (LRP) is proposed to solve these problems simultaneously. The problem extend from a practical perspective when the companies do not have their own vehicles to deliver their products. Considering in some real-life situations, arrival time at a customer will affect the customer’s satisfaction level or sales to the customer. Each customer may have a specific service time window during which s/he can be serviced, and a service vehicle must arrive within this time window to start its service. Therefore, this study combines the open location routing problem (OLRP) and time windows constraint into the open location routing problem with time windows (OLRPTW). This study proposes a branch-and-price algorithm to solve OLRPTW. This problem is solved by the simplex algorithm in the master problem. The elementary shortest path problem with resource constraints (ESPPRC) is used in this pricing problem which has the goal to generate feasible routes with negative reduced costs to be added to the restricted master problem (RMP). The OLRPTW instances are derived from three LRP benchmark data sets. The computational result indicates that the branch-and-price algorithm is comparable for small-medium instances. For large instances, it can solve instance with 200 customers and 10 depots to the optimality.

Akca, Z., Berger, R. T., & Ralphs, T. K. (2009). A branch-and-price algorithm for combined location and routing problems under capacity restrictions. Operations Research/ Computer Science Interfaces Series, 47, 309-330.
Baldacci, R., Mingozzi, A., & Calvo, R. W. (2011). An Exact Method for the Capacitated Location-Routing Problem. Operations Research, 59(5), 1284-1296.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research, 46(3), 316-329.
Barreto, S. (2004). Análise e modelização de problemas de localização-distribuição [Analysis and Modelling of Location-Routing Problems]. Dissertation, University of Aveiro, Aveiro, Portugal. (in Portuguese)
Belenguer, J.-M., Benavent, E., Prins, C., Prodhon, C., & Wolfler Calvo, R. (2011). A Branch-and-Cut method for the Capacitated Location-Routing Problem. Computers & Operations Research, 38(6), 931-941.
Berger, R. T., Coullard, C. R., & Daskin, M. S. (2007). Location-Routing Problems with Distance Constraints. Transportation Science, 41(1), 29-43.
Burks, R. E. (2006). An Adaptive Tabu Search Heuristic for the Location Routing Pickup and Delivery Problem with Time Windows with a Theater Distribution Application: Defense Technical Information Center.
Danna, E., & Le Pape, C. (2005). Branch-and-Price Heuristics: A Case Study on the Vehicle Routing Problem with Time Windows. In G. Desaulniers, J. Desrosiers & M. M. Solomon (Eds.), Column Generation. (pp. 99-129). Boston, MA: Springer US.
Dantzig, G. B., & Wolfe, P. (1960). Decomposition Principle for Linear Programs. Operations Research, 8(1), 101-111.
Dayarian, I., Crainic, T. G., Gendreau, M., & Rei, W. (2015). A branch-and-price approach for a multi-period vehicle routing problem. Computers & Operations Research, 55, 167-184.
Dell'Amico, M., Righini, G., & Salani, M. (2006). A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection. Transportation Science, 40(2), 235-247.
Desaulniers, G., Lessard, F., & Hadjar, A. (2008). Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Science, 42(3), 387-404.
Desrochers, M., & Soumis, F. (1989). A Column Generation Approach to the Urban Transit Crew Scheduling Problem. Transportation Science, 23(1), 1-13.
Desrosiers, J., Soumis, F., & Desrochers, M. (1984). Routing with time windows by column generation. Networks, 14(4), 545-565.
Dumitrescu, I. (2002). Constrained path and cycle problems. PhD thesis, The University of Melbourne. (in eng)
Feillet, D., Dejax, P., Gendreau, M., & Gueguen, C. (2004). An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, 44(3), 216-229.
Gündüz, H. I. (2011). The Single-Stage Location-Routing Problem with Time Windows. In J. W. Böse, H. Hu, C. Jahn, X. Shi, R. Stahlbock & S. Voß (Eds.), Computational Logistics: Second International Conference, ICCL 2011, Hamburg, Germany, September 19-22, 2011. Proceedings. (pp. 44-58). Berlin, Heidelberg: Springer Berlin Heidelberg.
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., & Arpin, D. (1986). An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research, 6(9), 291-310.
Laporte, G., Nobert, Y., & Pelletier, P. (1983). Hamiltonian location problems. European Journal of Operational Research, 12(1), 82-89.
Lübbecke, M. E., & Desrosiers, J. (2005). Selected Topics in Column Generation. Operations Research, 53(6), 1007-1023.
Min, H., Jayaraman, V., & Srivastava, R. (1998). Combined location-routing problems: A synthesis and future research directions. European Journal of Operational Research, 108(1), 1-15.
Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2), 649-672.
Ozbaygin, G., Ekin Karasan, O., Savelsbergh, M., & Yaman, H. (2017). A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transportation Research Part B: Methodological, 100, 115-137.
Parragh, S. N., & Cordeau, J.-F. (2017). Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows. Computers & Operations Research, 83, 28-44.
Ponboon, S., Qureshi, A. G., & Taniguchi, E. (2016). Branch-and-price algorithm for the location-routing problem with time windows. Transportation Research Part E: Logistics and Transportation Review, 86, 1-19.
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).
Rand, G. K. (1976). Methodological Choices in Depot Location Studies. Journal of the Operational Research Society, 27(1), 241-249.
Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39(2), 150-156.
Srivastava, R., & Benton, W. C. (1990). The location-routing problem: Considerations in physical distribution system design. Computers & Operations Research, 17(5), 427-435.
Tuzun, D., & Burke, L. I. (1999). Two-phase tabu search approach to the location routing problem. European Journal of Operational Research, 116(1), 87-99.
Watson, M., Lewis, S., Cacioppi, P., & Jayaraman, J. (2012). Supply Chain Network Design: Applying Optimization and Analytics to the Global Supply Chain: FT Press.
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.
Yu, V. F., & Lin, S.-Y. (2015). A simulated annealing heuristic for the open location-routing problem. Computers & Operations Research, 62, 184-196.