ABSTRACT The Vehicle Routing Problem with Synchronization (VRPSync) aims to minimise the total routing costs while considering synchronization requirements that must be fulfilled between tasks of different routes. These synchronization requirements are especially relevant when it is necessary to have tasks being performed by vehicles within given temporal offsets, a frequent requirement in applications where multiple vehicles, crews, materials, or other resources are involved in certain operations. Although several works in the literature have addressed this problem, mainly the deterministic version has been tackled so far. This paper presents a robust optimization approach for the VRPSync, taking into consideration the uncertainty in vehicle travel times between customers. This work builds on existing approaches in the literature to develop mathematical models for the Robust VRPSync, as well as a branch‐and‐cut algorithm to solve more difficult problem instances. A set of computational experiments is also devised and presented to obtain insights regarding key performance parameters of the mathematical models and the solution algorithm. The results suggest that solution strategies where certain standard problem constraints are only introduced if a candidate solution violates any of those constraints provide more consistent improvements than approaches that rely on tailor‐made cutting planes, added through separation routines. Furthermore, the analysis of the Price of Robustness indicators shows that the adoption of robust solutions can have a significant increase in the total costs, however, this increase quickly plateaus as budgets of uncertainty increase.

In the biobjective branch-and-bound literature, a key ingredient is objective branching, that is, to create smaller and disjoint subproblems in the objective space, obtained from the partial dominance of the lower bound set by the upper bound set. When considering three or more objective functions, however, applying objective branching becomes more complex, and its benefit has so far been unclear. In this paper, we investigate several ingredients that allow us to better exploit objective branching in a multiobjective setting. We extend the idea of probing to multiple objectives for the 0-1 case, enhance it in several ways, and show that, when coupled with objective branching, it results in significant speedups in terms of CPU times. We also show how to adapt it to the general integer case. Furthermore, we investigate cut generation based on the objective branching constraints. Besides, we generalize the best bound idea for node selection to multiple objectives, and we show that the proposed rules outperform, in the multiobjective literature, the commonly employed depth-first and breadth-first strategies. We also analyze problem-specific branching rules. We test the proposed ideas on available benchmark instances for three problem classes with three and four objectives, namely, the capacitated facility location problem, the uncapacitated facility location problem, and the knapsack problem. Our enhanced multiobjective branch-and-bound algorithm outperforms the best existing branch-and-bound–based approach and is the first to obtain competitive and even slightly better results than a state-of-the-art objective space search method on a subset of the problem classes. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported in whole, or in part, by the Austrian Science Fund [Grant P 31366]. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0299 .

For many real-world decision-making problems subject to uncertainty, it may be essential to deal with multiple and often conflicting objectives while taking the decision-makers' risk preferences into account. Conditional value-at-risk (CVaR) is a widely applied risk measure to address risk-averseness of the decision-makers. In this paper, we use the subset-based polyhedral representation of the CVaR to reformulate the bi-objective two-stage stochastic facility location problem presented in Nazemi et al. (2021). We propose an approximate cutting-plane method to deal with this more computationally challenging subset-based formulation. Then, the cutting plane method is embedded into the epsilon-constraint method, the balanced-box method, and a recently developed matheuristic method to address the bi-objective nature of the problem. Our computational results show the effectiveness of the proposed method. Finally, we discuss how incorporating an approximation of the subset-based polyhedral formulation affects the obtained solutions.

Motivated by their success in the single-objective domain, we propose a very simple linear programming-based matheuristic for tri-objective binary integer programming. To tackle the problem, we obtain lower bound sets by means of the vector linear programming solver Bensolve. Then, simple heuristic approaches, such as rounding and path relinking, are applied to this lower bound set to obtain high-quality approximations of the optimal set of trade-off solutions. The proposed algorithm is compared to a recently suggested algorithm which is, to the best of our knowledge, the only existing matheuristic method for tri-objective integer programming. Computational experiments show that our method produces a better approximation of the true Pareto front using significantly less time than the benchmark method on standard benchmark instances for the three-objective knapsack problem.

In bi-objective integer optimization the optimal result corresponds to a set of nondominated solutions. We propose a generic bi-objective branch-and-bound algorithm that uses a problem-independent branching rule exploiting available integer solutions and takes advantage of integer objective coefficients. The developed algorithm is applied to bi-objective facility location problems and the bi-objective set covering problem, as well as to the bi-objective team orienteering problem with time windows. In the latter case, lower bound sets are computed by means of column generation. Comparison with state-of-the-art exact algorithms shows the effectiveness of the proposed branch-and-bound algorithm.

In this article, we study the school bus routing and scheduling problem with transfers arising in the field of nonperiodic public transportation systems. It deals with the transportation of pupils from home to their school in the morning taking the possibility that pupils may change buses into account. Allowing transfers has several consequences. On the one hand, it allows more flexibility in the bus network structure and can, therefore, help to reduce operating costs. On the other hand, transfers have an impact on the service level: the perceived service quality is lower due to the existence of transfers; however, at the same time, user ride times may be reduced and, thus, transfers may also have a positive impact on service quality. The main objective is the minimization of the total operating costs. We develop a heuristic solution framework to solve this problem and compare it with two solution concepts that do not consider transfers. The impact of transfers on the service level in terms of time loss (or user ride time) and the number of transfers is analyzed. Our results show that allowing transfers reduces total operating costs significantly while average and maximum user ride times are comparable to solutions without transfers. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(2), 180-203 2015.

An increasing number of companies focus on customer satisfaction to increase the lifetime value of each customer. In vehicle routing, customer satisfaction is often a result of consistent service. Customers appreciate service at regular times of the day provided by the same driver each time. Additionally, drivers become more familiar with their tasks if they visit the same customers and service regions repeatedly. In this article, we survey literature that addresses service consistency in vehicle routing. We present early solution approaches, starting from the 1970s, that focus on reducing the operational complexity resulting from planning and executing new routes each day. One side benefit of these approaches is service consistency; therefore, many recent solution approaches devised for improving customer satisfaction are based on previous achievements. We classify the literature according to three consistency features: arrival time consistency, person-oriented consistency, and delivery consistency. For each feature, we survey different modeling concepts and measurements, demonstrate solution approaches, and examine the increase in cost of improving service consistency. We close the article by presenting challenging ideas for future research. © 2014 The Authors Networks Published by Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 192–213 2014

Abstract– The importance of customer satisfaction was identified by many industries as a key factor of competitive advantage. So, for companies in the small package shipping industry, it can be reasonable to increase the service quality even at the expense of transportation cost to gain customer loyalty. These companies noticed that customer satisfaction can be increased by providing consistent service in the form of visiting customers with the same driver at approximately the same time of the day over a certain time period. Motivated by this real‐world problem, the consistent vehicle routing problem (ConVRP) combines traditional vehicle routing constraints with the requirements for service consistency. This article presents a fast solution method called template‐based adaptive large neighborhood search for the described problem. Compared to state‐of‐the‐art heuristics, the developed algorithm is highly competitive on the available benchmark instances. Additionally, new test instances are provided. These seem to be more challenging due to the variation of different model parameters and consequently help to identify interesting effects. Finally, a relaxed variant of the original ConVRP is presented. In this variant, the departure times from the depot can be delayed to adjust the service times of the customers. Experiments show that allowing later departure times considerably improves the solution quality under tight consistency requirements. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 60–81 2014

Abstract In this article, we develop a heuristic two‐phase solution procedure for the dial‐a‐ride problem with two objectives. Besides the minimum cost objective a client centered objective has been defined. Phase one consists of an iterated variable neighborhood search‐based heuristic, generating approximate weighted sum solutions; phase two is a path relinking module, computing additional efficient solutions. Results for two sets of benchmark instances are reported. For the smaller instances, exact efficient sets are generated by means of the ϵ‐constraint method. Comparison shows that the proposed two‐phase method is able to generate high‐quality approximations of the true Pareto frontier. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009