Informs 2015

101 / 552

INFORMS Philadelphia – 2015
99
4 - An Exact Algorithm for the Pickup and Delivery Problem with
Time Windows and Scheduled Lines
Veaceslav Ghilas, PhD Student, Eindhoven University of
Technology, Den Dolech 2, Eindhoven, 5612 AZ, Netherlands,
, Jean - Francois Cordeau, Tom Van Woensel,
Emrah Demir
The Pickup and Delivery Problem with Time Windows and Scheduled Lines
(PDPTW-SL) concerns routing and scheduling a set of vehicles to serve a set of
freight requests such that a part of the journey can be carried out on a scheduled
public transportation line. We propose a branch-and-price algorithm for the
PDPTW-SL. A path-based set partitioning formulation is used as master problem,
and a variant of elementary shortest path problem with resource constraints is
studied as pricing problem.
5 - Signal Timing Detection Based on “Pseudo Vehicle Trajectory”
on the Spatial-temporal Map
Seyedamirali Mostafavizadeh, Graduate Research Assistant,
Rutgers University, Core 736, 96 Frelinghuysen Road,
Piscataway, NJ, 08854, United States of America,
, Peter J. Jin
This study introduces a new CCTV video based traffic signal timing detection
method. A spatial-temporal (ST) map is generated by stacking the raw pixels
along scan lines defined at the middle of each lane. Vehicles leave time-accurate
but space-distorted “pseudo trajectories” on ST map without the need of intensive
camera calibration. A moving Hough Line Transforms (MHLT) based method is
then introduced to detect straight lines (queuing) to generate the starting and
ending time of red lights.
SC20
20-Franklin 10, Marriott
Resource Allocation and Pricing in Cloud Computing
Cluster: Cloud Computing
Invited Session
Chair: Julie Ward, Distinguished Technologist, HP Labs, 1501 Page Mill
Rd, Palo Alto, CA, 94301, United States of America,
1 - Cost-efficient Cloud Computing
Vivek Farias, Associate Professor, MIT, 100 Main Street,
Cambridge, United States of America,
Muhammad Amjad, Andrew Li, Devavrat Shah
Cloud users today must navigate through a variety of pricing mechanisms, and
must contend with issues such as supply/demand forecasting and the high-
dimensional control problems that naturally arise when attempting to minimize
cost. We study the problem of computation under a deadline. We provide a
simple, scalable algorithm that requires no tuning and enjoys robust performance
guarantees. Along the way, we address a generalization of the classical Secretary
Problem and prophet inequalities.
2 - Results-based Pricing and Resource Allocation in
Cloud Computing
Filippo Balestrieri, HP Labs, 1501 Page Mill Rd, Palo Alto, CA,
94301, United States of America,
Julie Ward, Bernardo Huberman
Cloud services are sold today via a resource-based model, in which customers pay
per instance-period. New technologies for predicting job requirements and
completion times allow Cloud providers to consider new mechanisms. We
compare a resource-based model to a results-based mechanism, in which the
provider offers a menu of completion times and prices to each customer for his
specific job. We identify conditions under which one mechanism produces higher
revenue for the provider than the other.
3 - Selling Guaranteed Completion Times on the Cloud
Andrew Li, MIT Operations Research Center, 77 Massachusetts
Avenue, Bldg. E40-149, Cambridge, MA, 02139, United States of
America, Filippo Balestrieri, Julie Ward
In today’s cloud market, users execute their own jobs without a guarantee that
deadlines will be met. Instead, providers can take control of job execution and
charge for guaranteed completion times, but they face the joint challenges of
dynamically pricing such contracts and scheduling jobs to fulfill these contracts.
We address these challenges with a revenue management formulation, and apply
a fluid approximation that is computationally efficient and optimal for large
systems.
SC21
21-Franklin 11, Marriott
Applied Operations in Health Services: Research by
Bonder Scholars
Sponsor: Health Applications
Sponsored Session
Chair: Jonas Jonasson, Student, London Business School, Regent’s
Park, London, NW1 4SA, United Kingdom,
1 - Optimal Liver Cancer Surveillance in Hepatitis
C-infected Populations
Qiushi Chen, Turgay Ayer,
Jagpreet Chhatwal
Every 6-month surveillance for liver cancer is currently recommended in cirrhotic
hepatitis C patients, but the optimal surveillance policy remains unknown. We
develop a mixed-integer programming-based framework to analyze the most cost-
effective surveillance policies, and find that (1) the optimal surveillance interval
should depend on patients’ stage of hepatitis C and age, and (2) expanding
surveillance to earlier stage of hepatitis C improves the cost-effectiveness of HCC
surveillance.
2 - Ambulance Dispatching, Redeployment and Reallocation
Amir Ali Nasrollah Zadeh, Clemson University, Freeman Hall 129,
Clemson University, Clemson, SC, 29634, United States of
America, Amin Khademi, Cem Saydam,
Hari Rajagopalan, Maria Mayorga
Larger cities, expensive medical cares and heavy traffics have led to an increasing
number of medical emergency calls and associated costs. In this work we develop
an optimization model to find near-optimal solutions to ambulance dispatching,
redeployment and reallocation problem to minimize the total expected waiting
time of patients. We use approximate dynamic programming to find high-quality
solutions and compare our policies with current practices via a simulation model.
3 - Robust Post-donation Blood Screening under Uncertainty
Hadi El-amine, PhD Student, Virginia Tech, 250 Durham Hall
Perry St., Blacksburg, VA, 24061-0118, United States of America,
, Douglas Bish, Ebru Bish
Blood product safety, in terms of being free of transfusion-transmittable
infections, is crucial. Under uncertainties in testing parameters and prevalence
rates, various objective functions were considered in order to determine a
“robust” post-donation blood screening strategy that minimizes the risk of
releasing an infected unit of blood into the blood supply.
SC22
22-Franklin 12, Marriott
Adaptive Sampling and Selection in Simulation,
Medicine and Machine Learning
Sponsor: Applied Probability
Sponsored Session
Chair: Peter Frazier, Assistant Professor, Cornell University, 232 Rhodes
Hall, Cornell University, Ithaca, NY, 14850, United States of America,
1 - Large Scale Parallel Ranking and Selection
Susan Hunter, Purdue University, Grissom Hall,
315 N. Grant St., West Lafayette, IN, United States of America,
, Florin Ciocan, Eric Ni,
Shane Henderson
We discuss a new ranking and selection procedure that provides a good-selection
guarantee and is suitable for parallel implementation on large scale problems. Two
implementations, one using message-passing interface (MPI) and the other using
MapReduce, both perform well in a high-performance computing environment.
MPI is more efficient than MapReduce in the sense that cores are more heavily
utilized, but less robust to issues such as core failure that may arise in cloud
computing environments.
2 - Active Learning for Conjoint Analysis
Stephen Pallone, Cornell University, 290 Rhodes Hall, Cornell
University, Ithaca, NY, 14853, United States of America,
, Peter Frazier, Shane Henderson
Conjoint analysis is a method of learning a user’s preferences, where the user is
offered a set of alternatives and chooses the preferred option. We model the user’s
preferences as being characterized by a linear classifier, but allow for noise to
contaminate responses. The rate at which we learn depends on the alternatives
offered. We explore different policies for offering these alternatives, such as
knowledge gradient and greedy posterior entropy reduction, and analyze their
performance.
SC22