Search

The emergence of the SARS-CoV-2 virus and new viral variations with higher transmission and mortality rates have highlighted the urgency to accelerate vaccination to mitigate the morbidity and mortality of the COVID-19 pandemic. For this purpose, this paper formulates a new multi-vaccine, multi-depot location-inventory-routing problem for vaccine distribution. The proposed model addresses a wide variety of vaccination concerns: prioritizing age groups, fair distribution, multi-dose injection, dynamic demand, etc. To solve large-size instances of the model, we employ a Benders decomposition algorithm with a number of acceleration techniques. To monitor the dynamic demand of vaccines, we propose a new adjusted susceptible-infectious-recovered (SIR) epidemiological model, where infected individuals are tested and quarantined. The solution to the optimal control problem dynamically allocates the vaccine demand to reach the endemic equilibrium point. Finally, to illustrate the applicability and performance of the proposed model and solution approach, the paper reports extensive numerical experiments on a real case study of the vaccination campaign in France. The computational results show that the proposed Benders decomposition algorithm is 12 times faster, and its solutions are, on average, 16% better in terms of quality than the Gurobi solver under a limited CPU time. In terms of vaccination strategies, our results suggest that delaying the recommended time interval between doses of injection by a factor of 1.5 reduces the unmet demand up to 50%. Furthermore, we observed that the mortality is a convex function of fairness and an appropriate level of fairness should be adapted through the vaccination.

The vehicle routing problem with two-dimensional loading constraints (2L-CVRP) is a practical variant of the classic capacitated vehicle routing problem. A number of algorithms have been developed for the problem, but it is very difficult for the existing exact methods to optimally solve instances featuring with large rectangular items. To address this issue, a branch-and-price-and-cut (BPC) algorithm is proposed in this study. A novel data structure and a new dominance rule are developed to build an exact pricing algorithm that takes the loading constraints into account. Several valid inequalities are used to strengthen the linear relaxation. Extensive computational experiments were conducted on the benchmark instances of the 2L-CVRP, showing that the BPC algorithm outperforms all the existing exact methods for the problem in terms of the solution quality. Fourteen instances are solved to optimality for the first time. In particular, the size of solvable instances with large items is nearly doubled. Moreover, managerial insights about the impact of respecting the last-in-first-out constraint are also obtained.

The increasing penetration of renewable energy sources in the electricity grid brings new operational challenges. This brings up the need for effective means to provide demand response in spite of its distributed nature throughout the grid. Aggregators can be created to manage a set of such demand response resources, but deciding how to allocate an aggregator’s resources is an important problem. One of the aspects that needs more attention is the impact of the transmission system on these decisions. In this paper, we propose a short-term optimization model for allocating demand response(DR) resources as well as generation resources to supply external demand that is offered after the scheduling decision is made. The DR resources will only be available for use after the scheduling decision is made. Finally, our work also considers the impact of congestion in the transmission system when allocating DR. We propose the use of a semidefinite relaxation to provide a good initial point to solve our model with the aim of guaranteeing that we will find an optimal solution. Results from numerical tests with the IEEE 96-RTS and the ACTIVSG500 test grids are reported. We found that DR resources mitigates congestion management, allowing the generators to supply more of the external demand that is offered. Besides that, we observe that using our proposed solution methodology, we were able to obtain optimal solution for both cases studies, which is not the case when solving the original formulation for the ACTIVSG500 grid.

The growth of e-commerce has increased demand for last-mile deliveries, increasing the level of congestion in the existing transportation infrastructure in urban areas. Crowdsourcing deliveries can provide the additional capacity needed to meet the growing demand in a cost-effective way. We introduce a setting where a crowd-shipping platform sells heterogeneous products of different sizes from a central depot. Items sold vary from groceries to electronics. Some items must be delivered within a time window, whereas others need a customer signature. Furthermore, customer presence is not guaranteed, and some deliveries may need to be returned to the depot. Delivery requests are fulfilled by a fleet of professional drivers and a pool of crowd drivers. We present a crowd-shipping platform that standardizes crowd drivers’ capacities and compensates them to return undelivered packages back to the depot. We formulate a two-stage stochastic model, and we propose a branch and price algorithm to solve the problem exactly and a column generation heuristic to solve larger problems quickly. We further develop an analytical method to calculate upper bounds on the supply of vehicles and an innovative cohesive pricing problem to generate columns for the pool of crowd drivers. Computational experiments are carried out on modified Solomon instances with a pool of 100 crowd vehicles. The branch and price algorithm is able to solve instances of up to 100 customers. We show that the value of the stochastic solution can be as high as 18% when compared with the solution obtained from a deterministic simplification of the model. Significant cost reductions of up to 28% are achieved by implementing crowd drivers with low compensations or higher capacities. Finally, we evaluate what happens when crowd drivers are given the autonomy to select routes based on rational and irrational behavior. There is no cost increase when crowd drivers are rational and select routes that have a higher compensation first. However, when crowd drivers are irrational and select routes randomly, the cost can increase up to 4.2% for some instances.

A capacitated vehicle routing problem with two-dimensional loading constraints is addressed. Associated with each customer are a set of rectangular items, the total weight of the items, and a time window. Designing exact algorithms for the problem is very challenging because the problem is a combination of two NP-hard problems. An exact branch-and-price algorithm and an approximate counterpart are proposed to solve the problem. We introduce an exact dominance rule and an approximate dominance rule. To cope with the difficulty brought by the loading constraints, a new column generation mechanism boosted by a supervised learning model is proposed. Extensive experiments demonstrate the superiority of integrating the learning model in terms of CPU time and calls of the feasibility checker. Moreover, the branch-and-price algorithms are able to significantly improve the solutions of the existing instances from literature and solve instances with up to 50 customers and 103 items. Summary of Contribution: We wish to submit an original research article entitled “Learning-based branch-and-price algorithms for a vehicle routing problem with time windows and two-dimensional loading constraints” for consideration by IJOC. We confirm that this work is original and has not been published elsewhere, nor is it currently under for publication elsewhere. In this paper, we report a study in which we develop two branch-and-price algorithms with a machine learning model injected to solve a vehicle routing problem integrated the two-dimensional packing. Due to the complexity brought by the integration, studies on exact algorithms in this field are very limited. Our study is important to the field, because we develop an effective method to significantly mitigate computational burden brought by the packing problem so that exactness turns to be achievable within reasonable time budget. The approach can be generalized to the three-dimensional case by simply replacing the packing algorithm. It can also be adapted for other VRPs when high-dimensional loading constraints are concerned. Broadly speaking, the study is a typical example of adopting supervised learning to achieve acceleration for operations research algorithms, which expands the envelop of computing and operations research. Hence, we believe this manuscript is appropriate for publication by IJOC.

With the implementation of demand response programs and its increasing penetration in the power grid, various new challenges to the grid’s operation have emerged. As a consequence, optimizing the operation of the power grid and the allocation of demand response resources, in the short-term, medium-term and long-term, has become a fundamental problem. This survey presents a review of the optimization approaches in the literature for the integration of DR in three central problems in power systems planning, namely optimal power flow, unit commitment, and generation and transmission expansion planning. We also highlight important future research directions.