Operations Research, Systems Engineering and Industrial Engineering Commons^™

Iterated Local Search Algorithm For The Capacitated Team Orienteering Problem, Aldy Gunawan, Kien Ming Ng, Vincent F. Yu, Gordy Adiprasetyo, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

This paper focuses on a recent variant of the Orienteering Problem (OP), namely the Capacitated Team Orienteering Problem (CTOP). In this problem, each node is associated with a demand that needs to be satisfied and a score that need to be collected. Given a set of homogeneous fleet of vehicles, the main objective is to find a path for each available vehicle in order to maximize the total score, without violating the capacity and time budget of each vehicle. We propose an Iterated Local Search algorithm that has been applied in solving various variants of the OP. We propose two …

Robust Assignment Of Customer Orders With Uncertain Configurations In A Production Network For Aircraft Manufacturing, Jens Buergin, Philippe Blaettchen, Juri Kronenbitter, Katharina Molzahn, Yannick Schweizer, Caroline Strunz, Manuel Almagro, Frank Bitte, Stephan Ruehr, Marcello Urgo, Gisela Lanza

Research Collection Lee Kong Chian School Of Business

Production of multi-variant products in a network requires the assignment of customer orders to locations and periods. This is a highly complex planning task, as requirements of procurement, production, distribution, and sales have to be considered. Providing customers with the flexibility of configuring their ordered products after order assignment further increases the complexity of the planning task by taking uncertainty into account. Therefore, a robust optimisation model, using scenarios representing potential customer-specific order configurations, is introduced. By providing enough flexibility to handle maximum work overload caused by the potential order configurations at locations, a robust assignment of orders can be …

Adopt: Combining Parameter Tuning And Adaptive Operator Ordering For Solving A Class Of Orienteering Problems, Aldy Gunawan, Hoong Chuin Lau, Kun Lu

Research Collection School Of Computing and Information Systems

Two fundamental challenges in local search based metaheuristics are how to determine parameter configurations and design the underlying Local Search (LS) procedure. In this paper, we propose a framework in order to handle both challenges, called ADaptive OPeraTor Ordering (ADOPT). In this paper, The ADOPT framework is applied to two metaheuristics, namely Iterated Local Search (ILS) and a hybridization of Simulated Annealing and ILS (SAILS) for solving two variants of the Orienteering Problem: the Team Dependent Orienteering Problem (TDOP) and the Team Orienteering Problem with Time Windows (TOPTW). This framework consists of two main processes. The Design of Experiment (DOE) …

Instance-Specific Selection Of Aos Methods For Solving Combinatorial Optimisation Problems Via Neural Networks, Teck Hou (Deng Dehao) Teng, Hoong Chuin Lau, Aldy Gunawan

Research Collection School Of Computing and Information Systems

Solving combinatorial optimization problems using a fixed set of operators has been known to produce poor quality solutions. Thus, adaptive operator selection (AOS) methods have been proposed. But, despite such effort, challenges such as the choice of suitable AOS method and configuring it correctly for given specific problem instances remain. To overcome these challenges, this work proposes a novel approach known as I-AOS-DOE to perform Instance-specific selection of AOS methods prior to evolutionary search. Furthermore, to configure the AOS methods for the respective problem instances, we apply a Design of Experiment (DOE) technique to determine promising regions of parameter values …

Bounded Rank Optimization For Effective And Efficient Emergency Response, Pallavi Madhusudan Manohar, Pradeep Varakantham, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Effective placement of emergency response vehicles (such as ambulances, fire trucks, police cars) to deal with medical, fire or criminal activities can reduce the incident response time by few seconds, which in turn can potentially save a human life. Owing to its adoption in Emergency Medical Services (EMSs) worldwide, existing research on improving emergency response has focused on optimizing the objective of bounded time (i.e. number of incidents served in a fixed time). Due to the dependence of this objective on temporal uncertainty, optimizing the bounded time objective is challenging. In this paper, we propose a new objective referred to …

Reserved Optimisation: Handling Incident Priorities In Emergency Response Systems, Muralidhar Konda, Supriyo Ghosh, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Emergency (medical, fire or criminal) Management Systems(EMSs) are crucial for ensuring public safety and security. Typically in many cities, less than 20% of the cases received by EMSs belong to the extremely serious category and require immediate help. Rest of the incidents typically are less serious and thereby allow more flexibility in response time. Therefore, for efficient management of EMS requests, several EMSs now categorise an incoming emergency request into apriority level based on well studied “triaging” methods. Leading research on optimising emergency response has either focussed on data-driven models for settings with homogenous incidents or on generic heuristics (that …

Quadratic Two-Stage Stochastic Optimization With Coherent Measures Of Risk, Jie Sun, Li-Zhi Liao, Brian Rodrigues

Research Collection Lee Kong Chian School Of Business

A new scheme to cope with two-stage stochastic optimization problems uses a risk measure as the objective function of the recourse action, where the risk measure is defined as the worst-case expected values over a set of constrained distributions. This paper develops an approach to deal with the case where both the first and second stage objective functions are convex linear-quadratic. It is shown that under a standard set of regularity assumptions, this two-stage quadratic stochastic optimization problem with measures of risk is equivalent to a conic optimization problem that can be solved in polynomial time.

Integrated Cooperation And Competition In Multi-Agent Decision-Making, Kyle Hollins Wray, Akshat Kumar, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Observing that many real-world sequential decision problems are not purely cooperative or purely competitive, we propose a new model—cooperative-competitive process (CCP)—that can simultaneously encapsulate both cooperation and competition.First, we discuss how the CCP model bridges the gap between cooperative and competitive models. Next, we investigate a specific class of group-dominant CCPs, in which agents cooperate to achieve a common goal as their primary objective, while also pursuing individual goals as a secondary objective. We provide an approximate solution for this class of problems that leverages stochastic finite-state controllers.The model is grounded in two multi-robot meeting and box pushing domains that …

Resource-Constrained Scheduling For Maritime Traffic Management, Lucas Agussurja, Akshat Kumar, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We address the problem of mitigating congestion and preventing hotspots in busy water areas such as Singapore Straits and port waters. Increasing maritime traffic coupled with narrow waterways makes vessel schedule coordination for just-in-time arrival critical for navigational safety. Our contributions are: 1) We formulate the maritime traffic management problem based on the real case study of Singapore waters; 2) We model the problem as a variant of the resource-constrained project scheduling problem (RCPSP), and formulate mixed-integer and constraint programming (MIP/CP) formulations; 3) To improve the scalability, we develop a combinatorial Benders (CB) approach that is significantly more effective than …

Dispatch Guided Allocation Optimization For Effective Emergency Response, Supriyo Ghosh, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Effective emergency (medical, fire or criminal) response iscrucial for improving safety and security in urban environments. Recent research in improving effectiveness of emergency management systems (EMSs) has utilized data-drivenoptimization models for efficient allocation of emergency response vehicles (ERVs) to base locations. However, thesedata-driven optimization models either ignore the dispatchstrategy of ERVs (typically the nearest available ERV is dispatched to serve an incident) or employ myopic approaches(e.g., greedy approach based on marginal gain). This resultsin allocations that are not synchronised with the real evolution dynamics on the ground or can be improved significantly.To bridge this gap, we make the following contributions: …

Scalable Urban Mobile Crowdsourcing: Handling Uncertainty In Worker Movement, Shih-Fen Cheng, Cen Chen, Thivya Kandappu, Hoong Chuin Lau, Archan Misra, Nikita Jaiman, Randy Tandriansyah Daratan, Desmond Koh

Research Collection School Of Computing and Information Systems

In this article, we investigate effective ways of utilizing crowdworkers in providing various urban services. The task recommendation platform that we design can match tasks to crowdworkers based on workers’ historical trajectories and time budget limits, thus making recommendations personal and efficient. One major challenge we manage to address is the handling of crowdworker’s trajectory uncertainties. In this article, we explicitly allow multiple routine routes to be probabilistically associated with each worker. We formulate this problem as an integer linear program whose goal is to maximize the expected total utility achieved by all workers. We further exploit the separable structures …

Risk-Sensitive Stochastic Orienteering Problems For Trip Optimization In Urban Environments, Pradeep Varakantham, Akshat Kumar, Hoong Chuin Lau, William Yeoh

Research Collection School Of Computing and Information Systems

Orienteering Problems (OPs) are used to model many routing and trip planning problems. OPs are a variantof the well-known traveling salesman problem where the goal is to compute the highest reward path thatincludes a subset of vertices and has an overall travel time less than a specified deadline. However, the applicabilityof OPs is limited due to the assumption of deterministic and static travel times. To that end, Campbellet al. extended OPs to Stochastic OPs (SOPs) to represent uncertain travel times (Campbell et al. 2011). Inthis article, we make the following key contributions: (1) We extend SOPs to Dynamic SOPs (DSOPs), …

Law Enforcement Resource Optimization With Response Time Guarantees, Jonathan Chase, Jiali Du, Na Fu, Truc Viet Le, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In a security-conscious world, and with the rapid increase in the global urbanized population, there is a growing challenge for law enforcement agencies to efficiently respond to emergency calls. We consider the problem of spatially and temporally optimizing the allocation of law enforcement resources such that the quality of service (QoS) in terms of emergency response time can be guaranteed. To solve this problem, we provide a spatio-temporal MILP optimization model, which we learn from a real-world dataset of incidents and dispatching records, and solve by existing solvers. One key feature of our proposed model is the introduction of risk …

A Multiagent-Based Approach For Vehicle Routing By Considering Both Arriving On Time And Total Travel Time, Zhiguang Cao, Hongliang Guo, Jie Zhang

Research Collection School Of Computing and Information Systems

Arriving on time and total travel time are two important properties for vehicle routing. Existing route guidance approaches always consider them independently, because they may conflict with each other. In this article, we develop a semi-decentralized multiagent-based vehicle routing approach where vehicle agents follow the local route guidance by infrastructure agents at each intersection, and infrastructure agents perform the route guidance by solving a route assignment problem. It integrates the two properties by expressing them as two objective terms of the route assignment problem. Regarding arriving on time, it is formulated based on the probability tail model, which aims to …

Finding The 'Faster' Path In Vehicle Routing, Jing Guo, Yaoxin Wu, Xuexi Zhang, Le Zhang, Wei Chen, Zhiguang Cao, Hongliang Guo

Research Collection School Of Computing and Information Systems

In this study, the authors improve the faster criterion in vehicle routing by extending the bi-delta distribution to the bi-normal distribution, which is a reasonable assumption for travel time on each road link. Based on this assumption, theoretical models are built for an arbitrary path and subsequently adopted to evaluate two candidate paths through probabilistic comparison. Experimental results demonstrate the bi-normal behaviour of link travel time in practice, and verify the faster criterion's superiority in determining the optimal path either on an artificial network with bi-normal distribution modelling link travel time or on a real road network with real traffic …

Policy Gradient With Value Function Approximation For Collective Multiagent Planning, Duc Thien Nguyen, Akshat Kumar, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

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 …

A Selective-Discrete Particle Swarm Optimization Algorithm For Solving A Class Of Orienteering Problems, Aldy Gunawan, Vincent F. Yu, Perwira Redi, Parida Jewpanya, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

This study addresses a class of NP-hard problem called the Orienteering Problem (OP), which belongs to a well-known class of vehicle routing problems. In the OP, a set of nodes that associated with a location and a score is given. The time required to travel between each pair of nodes is known in advance. The total travel time is limited by a predetermined time budget. The objective is to select a subset of nodes to be visited that maximizes the total collected score within a path. The Team OP (TOP) is an extension of OP that incorporates multiple paths. Another …

Efficient Gate System Operations For A Multipurpose Port Using Simulation Optimization, Ketki Kulkarni, Trong Khiem Tran, Hai Wang, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Port capacity is determined by three major infrastructural resources namely, berths, yards and gates. Theadvertised capacity is constrained by the least of the capacities of the three resources. While a lot ofattention has been paid to optimizing berth and yard capacities, not much attention has been given toanalyzing the gate capacity. The gates are a key node between the land-side and sea-side operations in anocean-to-cities value chain. The gate system under consideration, located at an important port in an Asiancity, is a multi-class parallel queuing system with non-homogeneous Poisson arrivals. It is hard to obtaina closed form analytic approach for …

Combinatorial Auction For Transportation Matching Service: Formulation And Adaptive Large Neighborhood Search Heuristic, Baoxiang Li, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

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 …

Well-Tuned Algorithms For The Team Orienteering Problem With Time Windows, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen, Kun Lu

Research Collection School Of Computing and Information Systems

The Team Orienteering Problem with Time Windows (TOPTW) is the extension of the Orienteering Problem (OP) where each node is limited by a predefined time window during which the service has to start. The objective of the TOPTW is to maximize the total collected score by visiting a set of nodes with a limited number of paths. We propose two algorithms, Iterated Local Search and a hybridization of Simulated Annealing and Iterated Local Search (SAILS), to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical …

A Unified Framework For Vehicle Rerouting And Traffic Light Control To Reduce Traffic Congestion, Zhiguang Cao, Siwei Jiang, Jie Zhang, Hongliang Guo

Research Collection School Of Computing and Information Systems

As the number of vehicles grows rapidly each year, more and more traffic congestion occurs, becoming a big issue for civil engineers in almost all metropolitan cities. In this paper, we propose a novel pheromone-based traffic management framework for reducing traffic congestion, which unifies the strategies of both dynamic vehicle rerouting and traffic light control. Specifically, each vehicle, represented as an agent, deposits digital pheromones over its route, while roadside infrastructure agents collect the pheromones and fuse them to evaluate real-time traffic conditions as well as to predict expected road congestion levels in near future. Once road congestion is predicted, …

A Multi-Agent System For Coordinating Vessel Traffic, Teck-Hou Teng, Hoong Chuin Lau, Akshat Kumar

Research Collection School Of Computing and Information Systems

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 …

An Efficient Approach To Model-Based Hierarchical Reinforcement Learning, Zhuoru Li, Akshay Narayan, Tze-Yun Leong

Research Collection School Of Computing and Information Systems

We propose a model-based approach to hierarchical reinforcement learning that exploits shared knowledge and selective execution at different levels of abstraction, to efficiently solve large, complex problems. Our framework adopts a new transition dynamics learning algorithm that identifies the common action-feature combinations of the subtasks, and evaluates the subtask execution choices through simulation. The framework is sample efficient, and tolerates uncertain and incomplete problem characterization of the subtasks. We test the framework on common benchmark problems and complex simulated robotic environments. It compares favorably against the stateof-the-art algorithms, and scales well in very large problems.

Decentralized Planning In Stochastic Environments With Submodular Rewards, Rajiv Ranjan Kumar, Pradeep Varakantham, Akshat Kumar

Research Collection School Of Computing and Information Systems

Decentralized Markov Decision Process (Dec-MDP) providesa rich framework to represent cooperative decentralizedand stochastic planning problems under transition uncertainty.However, solving a Dec-MDP to generate coordinatedyet decentralized policies is NEXP-Hard. Researchershave made significant progress in providing approximate approachesto improve scalability with respect to number ofagents. However, there has been little or no research devotedto finding guarantees on solution quality for approximateapproaches considering multiple (more than 2 agents)agents. We have a similar situation with respect to the competitivedecentralized planning problem and the StochasticGame (SG) model. To address this, we identify models in thecooperative and competitive case that rely on submodular rewards,where we show …

Dynamic Repositioning To Reduce Lost Demand In Bike Sharing Systems, Supriyo Ghosh, Pradeep Varakantham, Yossiri Adulyasak, Patrick Jaillet

Research Collection School Of Computing and Information Systems

Bike Sharing Systems (BSSs) are widely adopted in major cities of the world due to concerns associated with extensive private vehicle usage, namely, increased carbon emissions, traffic congestion and usage of nonrenewable resources. In a BSS, base stations are strategically placed throughout a city and each station is stocked with a pre-determined number of bikes at the beginning of the day. Customers hire the bikes from one station and return them at another station. Due to unpredictable movements of customers hiring bikes, there is either congestion (more than required) or starvation (fewer than required) of bikes at base stations. Existing …

Managing Cities With Urban Computing, Singapore Management University

Research@SMU: Connecting the Dots

SMU Professors Lau Hoong Chuin and Lim Yun Fong are combining their mathematical, computational and business know-how to address challenges facing the inner-city deliveries of orders and shipments.

See the papers:

• A rolling horizon auction mechanism and virtual pricing of shipping capacity for urban consolidation centers
• Achieving economic and environmental sustainabilities in urban consolidation center with bicriteria auction
• Retail precinct management: A case of commercial decentralization in Singapore

Predicting The Performance Of Queues: A Data Analytic Approach, Kum Khiong Yang, Cayirli Tugba, Mei Wan Low

Research Collection Lee Kong Chian School Of Business

Existing models of multi-server queues with system transience and non-standard assumptions are either too complex or restricted in their assumptions to be used broadly in practice. This paper proposes using data analytics, combining computer simulation to generate the data and an advanced non-linear regression technique called the Alternating Conditional Expectation (ACE) to construct a set of easy-to-use equations to predict the performance of queues with a scheduled start and end time. Our results show that the equations can accurately predict the queue performance as a function of the number of servers, mean arrival load, session length and service time variability. …

Orienteering Problem: A Survey Of Recent Variants, Solution Approaches And Applications, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

Duplicate record, see https://ink.library.smu.edu.sg/sis_research/3271. The Orienteering Problem (OP) has received a lot of attention in the past few decades. The OP is a routing problem in which the goal is to determine a subset of nodes to visit, and in which order, so that the total collected score is maximized and a given time budget is not exceeded. A number of typical variants has been studied, such as the Team OP, the (Team) OP with Time Windows and the Time Dependent OP. Recently, a number of new variants of the OP was introduced, such as the Stochastic OP, the …

Orienteering Problem: A Survey Of Recent Variants, Solution Approaches And Applications, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

The Orienteering Problem (OP) has received a lot of attention in the past few decades. The OP is a routing problem in which the goal is to determine a subset of nodes to visit, and in which order, so that the total collected score is maximized and a given time budget is not exceeded. A number of typical variants has been studied, such as the Team OP, the (Team) OP with Time Windows and the Time Dependent OP. Recently, a number of new variants of the OP was introduced, such as the Stochastic OP, the Generalized OP, the Arc OP, …

Managing Egress Of Crowd During Infrastructure Disruption, Teck Hou Teng, Shih-Fen Cheng, Trong-Nghia Truong, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In a large indoor environment such as a sports arena or convention center, smooth egress of crowd after an event can be seriously affected if infrastructure such as elevators and escalators break down. In this paper, we propose a novel crowd simulator known as SIM-DISRUPT for simulating egress scenarios in non-emergency situations. To surface the impact of disrupted infrastructure on the egress of crowd, SIM-DISRUPT includes features that allow users to specify selective disruptions as well as strategies for controlling the distribution and egress choices of crowd. Using SIM-DISRUPT, we investigate effects of crowd distribution, egress choices and infrastructure disruptions …