We address the Home Health Care Delivery Problem (HHCDP), which is concerned with staff scheduling in the home health care industry. The goal is to schedule health care providers to serve patients at their homes that maximizes the total collected preference scores from visited patients subject to several constraints, such as workload of the health care providers, time budget for each provider and so on. The complexity lies in the possibility of cancellation of patient bookings dynamically, and the generated schedule should attempt to patients' preferred time windows. To cater to these requirements, we model the preference score as a step function which depends on the arrival time of the visit and the resulting problem as the Team Orienteering Problem (TOP) with soft Time Windows and Variable Profits. We propose a fast algorithm, Iterated Local Search (ILS), which has been widely used to solve other variants of the Orienteering Problem (OP). We first solve the modified benchmark Team OP with Time Window instances followed by randomly generated instances. We conclude that ILS is able to provide good solutions within reasonable computational times.

Decentralized (PO)MDPs provide an expressive framework for sequential decision making in a multiagent system. Given their computational complexity, recent research has focused on tractable yet practical subclasses of Dec-POMDPs. We address such a subclass called CDec-POMDP where the collective behavior of a population of agents affects the joint-reward and environment dynamics. Our main contribution is an actor-critic (AC) reinforcement learning method for optimizing CDec-POMDP policies. Vanilla AC has slow convergence for larger problems. To address this, we show how a particular decomposition of the approximate action-value function over agents leads to effective updates, and also derive a new way to train the critic based on local reward signals. Comparisons on a synthetic benchmark and a real world taxi fleet optimization problem show that our new AC approach provides better quality solutions than previous best approaches.

Port capacity is determined by three major infrastructural resources namely, berths, yards and gates. The advertised capacity is constrained by the least of the capacities of the three resources. While a lot of attention has been paid to optimizing berth and yard capacities, not much attention has been given to analyzing the gate capacity. The gates are a key node between the land-side and sea-side operations in an ocean-to-cities value chain. The gate system under consideration, located at an important port in an Asian city, is a multi-class parallel queuing system with non-homogeneous Poisson arrivals. It is hard to obtain a closed form analytical approach for such a system. In this paper, we describe an application of simulation techniques in analyzing the performance of gate operations. Further, we develop an optimization model that is integrated with simulation techniques to suggest efficient lane management policies for an outbound gate system.

This paper considers the problem of matching multiple shippers and multi-transporters for pickups and drop-offs, where the goal is to select a subset of group jobs (shipper bids) that maximizes profit. This is the underlying winner determination problem in an online auction-based vehicle sharing platform that matches transportation demand and supply, particularly in a B2B last-mile setting. Each shipper bid contains multiple jobs, and each job has a weight, volume, pickup location, delivery location and time window. On the other hand, each transporter bid specifies the vehicle capacity, available time periods, and a cost structure. This double-sided auction will be cleared by the platform to find a profit-maximizing match and corresponding routes while respecting shipper and transporter constraints. Compared to the classical Pickup-and-Delivery Problem, a key challenge is the dependency among jobs, more precisely, all jobs within a bid must either be accepted or rejected together and jobs within a bid may be assigned to different transporters. We formulate the mathematical model and propose an Adaptive Large Neighborhood Search approach to solve the problem heuristically. We also derive management insights obtained from our computational experiments.

Taxis (which include cars working with car aggregation systems such as Uber, Grab, Lyft etc.) have become a critical component in the urban transportation. While most research and applications in the context of taxis have focused on improving performance from a customer perspective, in this paper, we focus on improving performance from a taxi driver perspective. Higher revenues for taxi drivers can help bring more drivers into the system thereby improving availability for customers in dense urban cities.

Typically, when there is no customer on board, taxi drivers will cruise around to find customers either directly (on the street) or indirectly (due to a request from a nearby customer on phone or on aggregation systems). For such cruising taxis, we develop a Reinforcement Learning (RL) based system to learn from real trajectory logs of drivers to advise them on the right locations to find customers which maximize their revenue. There are multiple translational challenges involved in building this RL system based on real data, such as annotating the activities (e.g., roaming, going to a taxi stand, etc.) observed in trajectory logs, identifying the right features for a state, action space and evaluating against real driver performance observed in the dataset. We also provide a dynamic abstraction mechanism to improve the basic learning mechanism. Finally, we provide a thorough evaluation on a real world data set from a developed Asian city and demonstrate that an RL based system can provide significant benefits to the drivers.

Environmental, regulatory and resource constraints affects the safety and efficiency of vessels navigating in and out of the ports. Movement of vessels under such constraints must be coordinated for improving safety and efficiency. Thus, we frame the vessel coordination problem as a multi-agent path-finding (MAPF) problem. We solve this MAPF problem using a Coordinated Path-Finding (CPF) algorithm. Based on the local search paradigm, the CPF algorithm improves on the aggregated path quality of the vessels iteratively. Outputs of the CPF algorithm are the coordinated trajectories. The Vessel Coordination Module (VCM) described here is the module encapsulating our MAPF-based approach for coordinating vessel traffic. Our demonstration of VCM is conducted using two maritime scenarios of vessel traffic at two geographical regions of Singapore Waters.

Global increase in trade leads to congestion of maritime traffic at the ports. This often leads to increased maritime incidents or near-miss situations. To improve maritime safety while maintaining efficiency, movement of vessels needs to be better coordinated. Our work formulates this problem of coordinating the paths of vessels as a multi-agent path-finding(MAPF) problem. To address this problem, we introduce an innovative application of MAPF in the maritime domain known as Vessel Coordination Module (VCM). Based on the local search paradigm, VCM plans on a joint state space updated using the Electronic Navigation Charts (ENC) and the paths of vessels. We introduce the notion of path quality that measures the number of positions on a vessel path that is too close to some other vessels spatially and temporally. VCM aims to improve the overall path quality of vessels by improving path quality of selected vessels. Experiments are conducted on the Singapore Straits to evaluate and compare performance of our proposed approach in heterogeneous maritime scenario. Our experiment results show that VCM can improve the overall path quality of the vessels.

Larger vessels are bringing more cargoes into Singapore. Being one of the busiest ports, the safety of navigation in Singapore waters is becoming a real and urgent concern. Collision and near-miss incidents accounted for the majority of maritime incidents between 2011 and 2013. Incident investigations revealed human factor accounted for majority of the causal factors. Thus, it is evident that the existing approaches are inadequate. To improve the safety of navigation and boost the shipping capacity of Singapore waters, this work introduces a prescriptive system known as VTM-Prescribe capable of discovering coordinated paths that get vessels to move in coordinated manner. VTM-Prescribe discovers the set of coordinated paths using a search algorithm based on a local search paradigm. Treating vessels with circular ship domain, VTM-Prescribe prescribes appropriate paths to the vessels, possibly modifying their navigation routes and schedules. Meant for the real world, VTM-Prescribe learns coordination strategies that account for real world parameters such as speed-over-ground, maneuverability and turnaround time of vessels. Rigorous experiments performed using recent AIS data show VTM-Prescribe can reduce risk of navigation and increase the shipping capacity of Singapore waters. This is to be followed up with pilot tests of VTM-Prescribe in near-real world scenarios.

By integrating mapping and geospatial data into a county-level dataset for exploratory analysis, we will demonstrate how to provide useful insights for waste managers and local governments regarding spatial patterns of household hazardous waste (HHW) collection and how it changes over time. We use map-based visualization to display patterns of spatial intensity and county locations for HHW collection in California from 2004 to 2015. We use exploratory spatial data analytics methods to characterize the spatial distribution of HHW collected per person. When we considered the spatial relationships, we were able to develop and estimate a geographically-weighted regression to explain how different regional factors influence the amount of HHW collected. These factors include demographic characteristics, HHW management policy instruments, and environmental quality enforcement and consideration of these factors are necessary to create a successful recycling program.

Stochastic network design is a general framework for optimizing network connectivity. It has several applications in computational sustainability including spatial conservation planning, pre-disaster network preparation, and river network optimization. A common assumption in previous work has been made that network parameters (e.g., probability of species colonization) are precisely known, which is unrealistic in real-world settings. We therefore address the robust river network design problem where the goal is to optimize river connectivity for fish movement by removing barriers. We assume that fish passability probabilities are known only imprecisely, but are within some interval bounds. We then develop a planning approach that computes the policies with either high robust ratio or low regret. Empirically, our approach scales well to large river networks. We also provide insights into the solutions generated by our robust approach, which has significantly higher robust ratio than the baseline solution with mean parameter estimates.

Multiagent sequential decision making has seen rapid progress with formal models such as decentralized MDPs and POMDPs. However, scalability to large multiagent systems and applicability to real world problems remain limited. To address these challenges, we study multiagent planning problems where the collective behavior of a population of agents affects the joint-reward and environment dynamics. Our work exploits recent advances in graphical models for modeling and inference with a population of individuals such as collective graphical models and the notion of finite partial exchangeability in lifted inference. We develop a collective decentralized MDP model where policies can be computed based on counts of agents in different states. As the policy search space over counts is combinatorial, we develop a sampling based framework that can compute open and closed loop policies. Comparisons with previous best approaches on synthetic instances and a real world taxi dataset modeling supply-demand matching show that our approach significantly outperforms them w.r.t.solution quality.