Article
Management
Borzou Rostami, Guy Desaulniers, Fausto Errico, Andrea Lodi
Summary: This paper discusses a variant of the capacitated vehicle routing problem where travel times are uncertain and statistically correlated. By adopting a mean-variance approach, the aim is to plan reliable vehicle routes by penalizing routes with high travel time variability to reduce time variability.
OPERATIONS RESEARCH
(2021)
Article
Engineering, Multidisciplinary
Akang Wang, Anirudh Subramanyam, Chrysanthos E. Gounaris
Summary: This paper discusses the integration of branch-price-and-cut solvers with the robust optimization paradigm to address parametric uncertainty in vehicle routing problems. It proposes a novel approach that combines cutting-plane techniques with an advanced branch-price-and-cut algorithm to ensure complete robust feasibility against demand and travel time uncertainty. This approach is both modular and versatile, allowing the use of advanced branch-price-and-cut technologies without major modifications.
OPTIMIZATION AND ENGINEERING
(2022)
Article
Management
Artur Alves Pessoa, Michael Poss, Ruslan Sadykov, Francois Vanderbeck
Summary: The paper investigates the robust counterpart of the capacitated vehicle routing problem, introducing new techniques to improve algorithm efficiency and proposing a heuristic algorithm for problem-solving. Utilizing modern techniques and problem reformulation, the paper successfully solves almost all open instances.
OPERATIONS RESEARCH
(2021)
Article
Economics
Chenlu Ji, Rupal Mandania, Jiyin Liu, Anne Liret
Summary: This paper studies the problem of stochastic service task scheduling and vehicle routing for a telecommunication provider. Real-time data updates and re-optimization methods are used to improve on-time start of tasks.
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW
(2022)
Article
Management
Ihsan Yanikoglu, Tonguc Yavuz
Summary: This paper investigates a machine scheduling problem on unrelated parallel machines with the objective of minimizing the worst-case total tardiness. The authors propose a robust optimization model and discuss important properties of the mathematical formulation. The paper also addresses the issue of alternative optimal solutions for scheduling problems and presents a branch-and-price algorithm to solve realistic instances effectively. Numerical results demonstrate the effectiveness of the proposed approach in terms of optimality and improvement in objective function value.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Operations Research & Management Science
Maaike Hoogeboom, Yossiri Adulyasak, Wout Dullaert, Patrick Jaillet
Summary: The research proposes a robust vehicle routing problem with time window assignments (RVRP-TWA) that aims to simultaneously determine routes and time window assignments to minimize the expected travel time and the risk of violating time windows. The approach is based on estimating unknown travel time probability distributions using statistical data and solving the problem by iteratively generating subgradient cuts.
TRANSPORTATION SCIENCE
(2021)
Article
Economics
Felix Tamke, Udo Buscher
Summary: This paper introduces a new mixed integer linear programming (MILP) model for the vehicle routing problem with drones (VRPD) with two different time-oriented objective functions, and proposes new valid inequalities to strengthen the linear relaxation. The first branch-and-cut algorithm for the VRPD is developed, showing competitive performance in extensive numerical experiments. Integrating truck-drone tandems into transportation systems can improve delivery speed, reduce fleet size, and workload of truck drivers.
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL
(2021)
Article
Management
Patrick Healy, Nicolas Jozefowiez, Pierre Laroche, Franc Marchetti, Sebastien Martin, Zsuzsanna Roka
Summary: The Connected Max-k-Cut Problem is an extension of the well-known Max-Cut Problem, where the objective is to partition a graph into k connected subgraphs by maximizing the cost of inter-partition edges. The researchers propose a new integer linear program and a branch-and-cut algorithm for this problem, and also use graph isomorphism to structure the instances and facilitate their resolution. Extensive computational experiments show that, if k > 2, their approach outperforms existing algorithms in terms of quality.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Computer Science, Interdisciplinary Applications
Yaser Zarouk, Iraj Mahdavi, Javad Rezaeian, Francisco J. Santos-Arteaga
Summary: In this paper, we propose an optimization approach to solve the routing and scheduling problem in a heterogeneous transportation network. We introduce a hybrid meta-heuristic method based on genetic algorithm and simulated annealing to tackle the NP-hard quality of the model. Our approach improves upon the exact solution method and is applicable to various logistic structures and retail supply chains.
COMPUTERS & OPERATIONS RESEARCH
(2022)
Article
Engineering, Civil
Mengyan Jiang, Yi Zhang, Y. Zhang
Summary: This paper addresses the e-bus scheduling problem under travel time uncertainty using robust optimization approaches. The study shows that by increasing operational costs, the delays and battery energy shortages caused by travel time uncertainty can be effectively reduced. A trade-off between reducing infeasibility rates and increasing operational costs is necessary when choosing an appropriate uncertainty budget.
JOURNAL OF ADVANCED TRANSPORTATION
(2021)
Article
Management
Hu Qin, E. Su, Yilun Wang, Jiliu Li
Summary: This study investigates the electric vehicle relocation problem in one-way carsharing systems. By formulating a set-packing model and designing a branch-and-cut-and-price algorithm, the researchers found a solution that maximizes the total operational profit. Extensive computational experiments demonstrate the effectiveness of the proposed algorithm.
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE
(2022)
Article
Operations Research & Management Science
Ricardo Fukasawa, Joshua Gunter
Summary: The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a challenging variant of the deterministic problem due to the random nature of customer demands. Existing formulations for deterministic variants cannot be easily adapted to handle stochastic demands, as shown by our proof of the NP-hardness of solving the LP relaxation. Additionally, we provide a hardness result specifically for the case of independent normal demands.
OPERATIONS RESEARCH LETTERS
(2023)
Article
Transportation Science & Technology
Wenqi Gao, Zhixing Luo, Houcai Shen
Summary: In this study, an exact branch-and-price-and-cut algorithm is proposed to solve the time-dependent pollution routing problem. The algorithm tackles the route selection problem and the time-dependent elementary shortest path problem to find the optimal solution. Compared to a commercial solver, the algorithm shows better performance and finds optimal solutions for more instances in less time.
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES
(2023)
Article
Operations Research & Management Science
Guillaume Marques, Ruslan Sadykov, Remy Dupas, Jean-Christophe Deschamps
Summary: This paper studies the two-echelon capacitated vehicle routing problem with time windows and proposes a branch-cut-and-price algorithm to efficiently solve the problem. The experimental results show that the algorithm outperforms other methods in terms of computational efficiency.
TRANSPORTATION SCIENCE
(2022)
Article
Engineering, Electrical & Electronic
Teng Long, Qing-Shan Jia, Gongming Wang, Yu Yang
Summary: This paper presents an efficient and scalable real-time scheduling method for handling the charging demands of plug-in electric vehicles (PEV), demonstrating through simulations that the proposed method provides high computation efficiency and scalability while reducing operating costs for charging stations. Compared to existing methods, it outperforms in terms of charging policy search capabilities and performance guarantee.
IEEE TRANSACTIONS ON SMART GRID
(2021)
Article
Management
Kyoungmi Hwang, Kyungsik Lee, Sungsoo Park
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
(2017)
Article
Operations Research & Management Science
Seulgi Joung, Sungsoo Park
OPERATIONS RESEARCH LETTERS
(2017)
Article
Computer Science, Hardware & Architecture
Seulgi Joung, Sungsoo Park
Article
Business
Yerin Kim, Daemook Kang, Mingoo Jeon, Chungmok Lee
ENGINEERING ECONOMIST
(2019)
Article
Management
Chungmok Lee
Summary: This paper addresses the Electric-Vehicle Routing Problem with nonlinear charging time and proposes an algorithm based on the segmentation of vehicle tour and extended charging stations network to minimize total travel and charging times. The proposed branch-and-price method on the extended charging station network can solve moderate-sized problems to optimality, as confirmed by an extensive computational study.
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
(2021)
Article
Operations Research & Management Science
Munjeong Kang, Chungmok Lee
Summary: There are recent attempts to utilize drones in logistics, considering the collaboration between multiple drones with different characteristics and trucks in delivery services. A heterogeneous drone-truck routing problem is proposed, with a mixed-integer programming formulation and an exact algorithm based on logic-based Benders decomposition, outperforming current solvers.
TRANSPORTATION SCIENCE
(2021)
Article
Operations Research & Management Science
Seohee Kim, Chungmok Lee
Summary: This paper addresses a variant of the bandwidth packing problem to maximize total revenue by determining paths for selected demands on a telecommunication network with given arc capacities, considering queuing delays as penalties. Mathematical formulation as a non-linear integer programming problem is presented due to queuing delays, linearized to a MIP problem solvable by Cplex, and a branch-and-price approach proposed for efficient column generation problem solving with dynamic programming algorithms. Computational experiments show significant improvement over state-of-the-art MIP solvers in computational times and assert the benefits of a robust approach through Monte-Carlo simulation study.
ANNALS OF OPERATIONS RESEARCH
(2021)
Article
Management
Chungmok Lee
Summary: This study focuses on optimization problems with uncertain coefficients and proposes an F-optimal solution algorithm, which guarantees to remain the best solution even after additional F probings of uncertain data. The research shows that the proposed approach can find the true optimal solutions at very high percentages, even with small numbers of probings.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Operations Research & Management Science
Jaehyeon Ryu, Sungsoo Park
Summary: In this study, we consider the robust single-source capacitated facility location problem with uncertainty in customer demands. We propose an allocation-based formulation derived by Dantzig-Wolfe decomposition and a branch-and-price algorithm to efficiently solve the problem. Computational experiments show that our branch-and-price algorithm outperforms CPLEX in many cases and the robustness of solutions can be significantly improved with small additional costs.
EURO JOURNAL ON TRANSPORTATION AND LOGISTICS
(2022)
Article
Economics
Junyoung Kim, Byungju Goo, Youngjoo Roh, Chungmok Lee, Kyungsik Lee
Summary: The airport gate assignment problem aims to efficiently allocate gates to flights, taking into account unpredictable factors such as air traffic demands and weather conditions. A robust gate assignment plan is crucial for airport operators to handle flight schedule deviations effectively.
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL
(2023)
Article
Computer Science, Interdisciplinary Applications
Kiho Seo, Seulgi Joung, Chungmok Lee, Sungsoo Park
Summary: This paper presents an improved Benders decomposition algorithm with enhanced convergence. A new cut selection scheme and separation framework are proposed. Experimental results demonstrate the advantages of the algorithm in terms of convergence speed and computational time.
INFORMS JOURNAL ON COMPUTING
(2022)
Article
Operations Research & Management Science
Chungmok Lee, Donghyun Cho, Sungsoo Park
MILITARY OPERATIONS RESEARCH
(2019)
Article
Operations Research & Management Science
Kyoungmi Hwang, Dohyun Kim, Kyungsik Lee, Chungmok Lee, Sungsoo Park
ANNALS OF OPERATIONS RESEARCH
(2017)
Article
Operations Research & Management Science
Jiyoung Choi, Chungmok Lee, Sungsoo Park
ANNALS OF OPERATIONS RESEARCH
(2018)