A Framework for Multi-stage Bonus Allocation in Meal-Delivery Platform

Online meal delivery is undergoing explosive growth, as this service is becoming increasingly fashionable. A meal delivery platform aims to provide efficient services for customers and restaurants. However, in reality, several hundred thousand orders are canceled per day in the Meituan meal delivery platform since they are not accepted by the crowdsoucing drivers, which is … Read more

An exact (re)optimization framework for real-time traffic management

In real-time traffic management, a new schedule for the vehicles must be computed whenever a deviation from the current plan is detected, or periodically after some time. If this time interval is relatively small, then each two consecutive instances are likely to be similar. We exploit this aspect to derive an exact reoptimization framework for … Read more

Exact Methods for Solving Traveling Salesman Problems with Pickup and Delivery in Real Time

The Traveling Salesman Problem with Pickup and Delivery (TSPPD) describes the problem of finding a minimum cost path in which pickups precede their associated deliveries. The TSPPD is particularly important in the growing field of Dynamic Pickup and Delivery Problems (DPDP). These include the many-to-many Dial-A-Ride Problems (DARP) of companies such as Uber and Lyft, … Read more

Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making

We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … Read more

Approximating the Stability Region for Binary Mixed-Integer Programs

We consider optimization problems with some binary variables, where the objective function is linear in these variables. The stability region of a given solution of such a problem is the polyhedral set of objective coefficients for which the solution is optimal. A priori knowledge of this set provides valuable information for sensitivity analysis and re-optimization … Read more