Alejandro Toriello The Lovasz theta function is a semidefinite programming (SDP) relaxation for the maximum weighted stable set problem, which is tight for perfect graphs. However, even for perfect graphs, there is no known rounding method guaranteed to extract an optimal stable set from the SDP solution. In this paper, we develop a novel rounding scheme for … Read more
Motivated by applications in e-commerce logistics and production planning where orders (or items, or jobs) arrive at different times and must be dispatched or processed in batches, we consider a multi-vehicle dispatching problem that captures the tension between waiting for orders to arrive and the economies of scale due to batching. Our model extends the … Read more
We study a system in which a common delivery fleet provides service to both same-day delivery (SDD) and next-day delivery (NDD) orders placed by e-retail customers who are sensitive to delivery prices. We develop a model of the system and optimize with respect to two separate objectives. First, empirical research suggests that fulfilling e-retail orders … Read more
Motivated by applications in cloud computing, we study a temporal bin packing problem with jobs that occupy half of a bin’s capacity. An instance is given by a set of jobs, each with a start and end time during which it must be processed, i.e., assigned to a bin. A bin can accommodate two jobs … Read more
Motivated by applications in e-commerce logistics where orders or items arrive at different times and must be dispatched or processed in batches, we propose the subadditive dispatching problem (SAD), a strongly NP-hard problem defined by a set of orders with release times and a non-decreasing subadditive dispatch time function. A single uncapacitated vehicle must dispatch … Read more
We study a two-stage natural disaster management problem modeled as a stochastic program, where the first stage consists of a facility location problem, deciding where to open facilities and pre-allocate resources such as medical and food kits, and the second stage is a fixed-charge transportation problem, routing resources to affected areas after observing a disaster. … Read more
Motivated by access and equity issues in e-commerce, we study the design of same-day delivery (SDD) systems under the assumption that service regions are allowed to vary over the course of the day; equivalently, that customers in different locations may have access to SDD for different lengths of time over the service day or may … Read more
Motivated by applications in cloud computing, we study interval scheduling problems exhibiting economies of scale. An instance is given by a set of jobs, each with start time, end time, and a function representing the cost of scheduling a subset of jobs on the same machine. Specifically, we focus on the max-weight function and non-negative, … Read more
Parcel logistics services play a vital and growing role in economies worldwide, with customers demanding faster delivery of nearly everything to their homes. To move larger volumes more cost effectively, express carriers use sort technologies to consolidate parcels that share similar geographic and service characteristics for reduced per-unit handling and transportation costs. This paper focuses … Read more
We study the linked tactical design problems of fleet sizing and partitioning a service region into vehicle routing zones for same-day delivery (SDD) systems. Existing SDD studies focus primarily on operational dispatch problems and do not consider system design questions. Prior work on SDD system design has not considered the fleet sizing decision when a … Read more