Open Access. Powered by Scholars. Published by Universities.®
Operations Research, Systems Engineering and Industrial Engineering Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Optimization (11)
- Scheduling (11)
- Uncertainty (8)
- Tabu search (6)
- Combinatorial optimization (5)
-
- Multi-agent systems (5)
- Reinforcement learning (5)
- Vehicle routing problem (5)
- Adaptive large neighborhood search (4)
- Algorithms (4)
- Logistics (4)
- Multi agent systems (4)
- Orienteering Problem (4)
- Singapore (4)
- Analytical models (3)
- Artificial intelligence (3)
- Auction (3)
- Constrained optimization (3)
- Decision making (3)
- Design of experiments (3)
- Multi-Agent Systems (3)
- Preferences (3)
- Problem solving (3)
- Autonomous agents (2)
- Benchmarking (2)
- Budget control (2)
- Commodity Trading (2)
- Cross-docking (2)
- DCOP (2)
- DEC-POMDP (2)
- Publication Year
- Publication
- Publication Type
Articles 61 - 90 of 242
Full-Text Articles in Operations Research, Systems Engineering and Industrial Engineering
Orienteering Problem: A Survey Of Recent Variants, Solution Approaches And Applications, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen
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, …
Enhancing Local Search With Adaptive Operator Ordering And Its Application To The Time Dependent Orienteering Problem, Aldy Gunawan, Hoong Chuin Lau, Kun Lu
Enhancing Local Search With Adaptive Operator Ordering And Its Application To The Time Dependent Orienteering Problem, Aldy Gunawan, Hoong Chuin Lau, Kun Lu
Research Collection School Of Computing and Information Systems
No abstract provided.
Designing And Comparing Multiple Portfolios Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir
Designing And Comparing Multiple Portfolios Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir
Research Collection School Of Computing and Information Systems
Algorithm portfolios seek to determine an effective set of algorithms that can be used within an algorithm selection framework to solve problems. A limited number of these portfolio studies focus on generating different versions of a target algorithm using different parameter configurations. In this paper, we employ a Design of Experiments (DOE) approach to determine a promising range of values for each parameter of an algorithm. These ranges are further processed to determine a portfolio of parameter configurations, which would be used within two online Algorithm Selection approaches for solving different instances of a given combinatorial optimization problem effectively. We …
Strategic Planning For Setting Up Base Stations In Emergency Medical Systems, Supriyo Ghosh, Pradeep Varakantham
Strategic Planning For Setting Up Base Stations In Emergency Medical Systems, Supriyo Ghosh, Pradeep Varakantham
Research Collection School Of Computing and Information Systems
Emergency Medical Systems (EMSs) are an important component of public health-care services. Improving infrastructure for EMS and specifically the construction of base stations at the ”right” locations to reduce response times is the main focus of this paper. This is a computationally challenging task because of the: (a) exponentially large action space arising from having to consider combinations of potential base locations, which themselves can be significant; and (b) direct impact on the performance of the ambulance allocation problem, where we decide allocation of ambulances to bases. We present an incremental greedy approach to discover the placement of bases that …
Dual Formulations For Optimizing Dec-Pomdp Controllers, Akshat Kumar, Hala Mostafa, Shlomo Zilberstein
Dual Formulations For Optimizing Dec-Pomdp Controllers, Akshat Kumar, Hala Mostafa, Shlomo Zilberstein
Research Collection School Of Computing and Information Systems
Decentralized POMDP is an expressive model for multi-agent planning. Finite-state controllers (FSCs)---often used to represent policies for infinite-horizon problems---offer a compact, simple-to-execute policy representation. We exploit novel connections between optimizing decentralized FSCs and the dual linear program for MDPs. Consequently, we describe a dual mixed integer linear program (MIP) for optimizing deterministic FSCs. We exploit the Dec-POMDP structure to devise a compact MIP and formulate constraints that result in policies executable in partially-observable decentralized settings. We show analytically that the dual formulation can also be exploited within the expectation maximization (EM) framework to optimize stochastic FSCs. The resulting EM algorithm …
Self-Organizing Neural Network For Adaptive Operator Selection In Evolutionary Search, Teck Hou Teng, Stephanus Daniel Handoko, Hoong Chuin Lau
Self-Organizing Neural Network For Adaptive Operator Selection In Evolutionary Search, Teck Hou Teng, Stephanus Daniel Handoko, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
Evolutionary Algorithm is a well-known meta-heuristics paradigm capable of providing high-quality solutions to computationally hard problems. As with the other meta-heuristics, its performance is often attributed to appropriate design choices such as the choice of crossover operators and some other parameters. In this chapter, we propose a continuous state Markov Decision Process model to select crossover operators based on the states during evolutionary search. We propose to find the operator selection policy efficiently using a self-organizing neural network, which is trained offline using randomly selected training samples. The trained neural network is then verified on test instances not used for …
Approximate Inference Using Dc Programming For Collective Graphical Models, Duc Thien Nguyen, Akshat Kumar, Hoong Chuin Lau, Daniel Sheldon
Approximate Inference Using Dc Programming For Collective Graphical Models, Duc Thien Nguyen, Akshat Kumar, Hoong Chuin Lau, Daniel Sheldon
Research Collection School Of Computing and Information Systems
Collective graphical models (CGMs) provide a framework for reasoning about a population of independent and identically distributed individuals when only noisy and aggregate observations are given. Previous approaches for inference in CGMs work on a junction-tree representation, thereby highly limiting their scalability. To remedy this, we show how the Bethe entropy approximation naturally arises for the inference problem in CGMs. We reformulate the resulting optimization problem as a difference-of-convex functions program that can capture different types of CGM noise models. Using the concave-convex procedure, we then develop a scalable message-passing algorithm. Empirically, our approach is highly scalable and accurate for …
Reinforcement Learning Framework For Modeling Spatial Sequential Decisions Under Uncertainty: (Extended Abstract), Truc Viet Le, Siyuan Liu, Hoong Chuin Lau
Reinforcement Learning Framework For Modeling Spatial Sequential Decisions Under Uncertainty: (Extended Abstract), Truc Viet Le, Siyuan Liu, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
We consider the problem of trajectory prediction, where a trajectory is an ordered sequence of location visits and corresponding timestamps. The problem arises when an agent makes sequential decisions to visit a set of spatial locations of interest. Each location bears a stochastic utility and the agent has a limited budget to spend. Given the agent's observed partial trajectory, our goal is to predict the remaining trajectory. We propose a solution framework to the problem considering both the uncertainty of utility and the budget constraint. We use reinforcement learning (RL) to model the underlying decision processes and inverse RL to …
Simultaneous Optimization And Sampling Of Agent Trajectories Over A Network, Hala Mostafa, Akshat Kumar, Hoong Chuin Lau
Simultaneous Optimization And Sampling Of Agent Trajectories Over A Network, Hala Mostafa, Akshat Kumar, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
We study the problem of optimizing the trajectories of agents moving over a network given their preferences over which nodes to visit subject to operational constraints on the network. In our running example, a theme park manager optimizes which attractions to include in a day-pass to maximize the pass’s appeal to visitors while keeping operational costs within budget. The first challenge in this combinatorial optimization problem is that it involves quantities (expected visit frequencies of each attraction) that cannot be expressed analytically, for which we use the Sample Average Approximation. The second challenge is that while sampling is typically done …
Robust Influence Maximization, Meghna Lowalekar, Pradeep Varakantham, Akshat Kumar
Robust Influence Maximization, Meghna Lowalekar, Pradeep Varakantham, Akshat Kumar
Research Collection School Of Computing and Information Systems
Influence Maximization is the problem of finding a fixed size set of nodes, which will maximize the expected number of influenced nodes in a social network. The number of influenced nodes is dependent on the influence strength of edges that can be very noisy. The noise in the influence strengths can be modeled using a random noise or adversarial noise model. It has been shown that all random processes that independently affect edges of the graph can be absorbed into the activation probabilities themselves and hence random noise can be captured within the independent cascade model. On the other hand, …
Shortest Path Based Decision Making Using Probabilistic Inference, Akshat Kumar
Shortest Path Based Decision Making Using Probabilistic Inference, Akshat Kumar
Research Collection School Of Computing and Information Systems
We present a new perspective on the classical shortest path routing (SPR) problem in graphs. We show that the SPR problem can be recast to that of probabilistic inference in a mixture of simple Bayesian networks. Maximizing the likelihood in this mixture becomes equivalent to solving the SPR problem. We develop the well known Expectation-Maximization (EM) algorithm for the SPR problem that maximizes the likelihood, and show that it does not get stuck in a locally optimal solution. Using the same probabilistic framework, we then address an NP-Hard network design problem where the goal is to repair a network of …
Robust Execution Strategies For Project Scheduling With Unreliable Resources And Stochastic Durations, Na Fu, Hoong Chuin Lau, Pradeep Varakantham
Robust Execution Strategies For Project Scheduling With Unreliable Resources And Stochastic Durations, Na Fu, Hoong Chuin Lau, Pradeep Varakantham
Research Collection School Of Computing and Information Systems
The resource-constrained project scheduling problem with minimum and maximum time lags (RCPSP/max) is a general model for resource scheduling in many real-world problems (such as manufacturing and construction engineering). We consider RCPSP/max problems where the durations of activities are stochastic and resources can have unforeseen breakdowns. Given a level of allowable risk, (Formula presented.), our mechanisms aim to compute the minimum robust makespan execution strategy. Robust makespan for an execution strategy is any makespan value that has a risk less than (Formula presented.). The risk for a makespan value, (Formula presented.) given an execution strategy, is the probability that a …
Designing Bus Transit Services For Routine Crowd Situations At Large Event Venues, Jianli Du, Shih-Fen Cheng, Hoong Chuin Lau
Designing Bus Transit Services For Routine Crowd Situations At Large Event Venues, Jianli Du, Shih-Fen Cheng, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
We are concerned with the routine crowd management problem after a major event at a known venue. Without properly design complementary transport services, such sudden crowd build-ups will overwhelm the existing infrastructure. In this paper, we introduce a novel flow-rate based model to model the dynamic movement of passengers over the transportation flow network. Based on this basic model, an integer linear programming model is proposed to solve the bus transit problem permanently. We validate our model against a real scenario in Singapore, where a newly constructed mega-stadium hosts various large events regularly. The results show that the proposed approach …
Ad-Hoc Automated Teller Machine Failure Forecast And Field Service Optimization, Michelle L. F. Cheong, Ping Shung Koo, B. Chandra Babu
Ad-Hoc Automated Teller Machine Failure Forecast And Field Service Optimization, Michelle L. F. Cheong, Ping Shung Koo, B. Chandra Babu
Research Collection School Of Computing and Information Systems
As part of its overall effort to maintain good customer service while managing operational efficiency and reducing cost, a bank in Singapore has embarked on using data and decision analytics methodologies to perform better ad-hoc ATM failure forecasting and plan the field service engineers to repair the machines. We propose using a combined Data and Decision Analytics Framework which helps the analyst to first understand the business problem by collecting, preparing and exploring data to gain business insights, before proposing what objectives and solutions can and should be done to solve the problem. This paper reports the work in analyzing …
Probabilistic Inference Based Message-Passing For Resource Constrained Dcops, Supriyo Ghosh, Akshat Kumar, Pradeep Varakantham
Probabilistic Inference Based Message-Passing For Resource Constrained Dcops, Supriyo Ghosh, Akshat Kumar, Pradeep Varakantham
Research Collection School Of Computing and Information Systems
Distributed constraint optimization (DCOP) is an important framework for coordinated multiagent decision making. We address a practically useful variant of DCOP, called resource-constrained DCOP (RC-DCOP), which takes into account agents’ consumption of shared limited resources. We present a promising new class of algorithm for RC-DCOPs by translating the underlying co- ordination problem to probabilistic inference. Using inference techniques such as expectation- maximization and convex optimization machinery, we develop a novel convergent message-passing algorithm for RC-DCOPs. Experiments on standard benchmarks show that our approach provides better quality than previous best DCOP algorithms and has much lower failure rate. Comparisons against an …
History-Based Controller Design And Optimization For Partially Observable Mdps, Akshat Kumar, Shlomo Zilberstein
History-Based Controller Design And Optimization For Partially Observable Mdps, Akshat Kumar, Shlomo Zilberstein
Research Collection School Of Computing and Information Systems
Partially observable MDPs provide an elegant framework forsequential decision making. Finite-state controllers (FSCs) are often used to represent policies for infinite-horizon problems as they offer a compact representation, simple-to-execute plans, and adjustable tradeoff between computational complexityand policy size. We develop novel connections between optimizing FSCs for POMDPs and the dual linear programfor MDPs. Building on that, we present a dual mixed integer linear program (MIP) for optimizing FSCs. To assign well-defined meaning to FSC nodes as well as aid in policy search, we show how to associate history-based features with each FSC node. Using this representation, we address another challenging …
Retail Precinct Management: A Case Of Commercial Decentralization In Singapore, Robert De Souza, Hoong Chuin Lau, Mark Goh, Lindawati, Wee-Siong Ng, Puay-Siew Tan
Retail Precinct Management: A Case Of Commercial Decentralization In Singapore, Robert De Souza, Hoong Chuin Lau, Mark Goh, Lindawati, Wee-Siong Ng, Puay-Siew Tan
Research Collection School Of Computing and Information Systems
The synchronized last mile logistics concept seeks to address, through coordinated collaboration, several challenges that hinder reliability, cost efficiency, effective resource planning, scheduling and utilization; and increasingly, sustainability objectives. Subsequently, the meeting of service level and contractual commitments are competitively impacted with any loss of efficiency. These challenges, against a backdrop of Singapore, can essentially be addressed in selected industry sectors through a better understanding of logistics structures; innovative supply chain designs and coordination of services, operations and processes coupled with concerted policies and supply chain strategies.
Direct: A Scalable Approach For Route Guidance In Selfish Orienteering Problems, Pradeep Varakantham, Hala Mostafa, Na Fu, Hoong Chuin Lau
Direct: A Scalable Approach For Route Guidance In Selfish Orienteering Problems, Pradeep Varakantham, Hala Mostafa, Na Fu, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
We address the problem of crowd congestion at venues like theme parks, museums and world expos by providing route guidance to multiple selfish users (with budget constraints) moving through the venue simultaneously. To represent these settings, we introduce the Selfish Orienteering Problem (SeOP) that combines two well studied problems from literature, namely Orienteering Problem (OP) and Selfish Routing (SR). OP is a single agent routing problem where the goal is to minimize latency (or maximize reward) in traversing a subset of nodes while respecting budget constraints. SR is a game between selfish agents looking for minimum latency routes from source …
Predicting Bundles Of Spatial Locations From Learning Revealed Preference Data, Truc Viet Le, Siyuan Liu, Hoong Chuin Lau, Ramayya Krishnan
Predicting Bundles Of Spatial Locations From Learning Revealed Preference Data, Truc Viet Le, Siyuan Liu, Hoong Chuin Lau, Ramayya Krishnan
Research Collection School Of Computing and Information Systems
We propose the problem of predicting a bundle of goods, where the goods considered is a set of spatial locations that an agent wishes to visit. This typically arises in the tourism setting where attractions can often be bundled and sold as a package to visitors. While the problem of predicting future locations given the current and past trajectories is well-established, we take a radical approach by looking at it from an economic point of view. We view an agent's past trajectories as revealed preference (RP) data, where the choice of locations is a solution to an optimisation problem according …
Near-Optimal Decentralized Power Supply Restoration In Smart Grids, Pritee Agrawal, Akshat Kumar, Pradeep Varakantham
Near-Optimal Decentralized Power Supply Restoration In Smart Grids, Pritee Agrawal, Akshat Kumar, Pradeep Varakantham
Research Collection School Of Computing and Information Systems
Next generation of smart grids face a number of challenges including co-generation from intermittent renewable power sources, a shift away from monolithic control due to increased market deregulation, and robust operation in the face of disasters. Such heterogeneous nature and high operational readiness requirement of smart grids necessitates decentralized control for critical tasks such as power supply restoration (PSR) after line failures. We present a novel multiagent system based approach for PSR using Lagrangian dual decomposition. Our approach works on general graphs, provides provable quality-bounds and requires only local message-passing among different connected sub-regions of a smart grid, enabling decentralized …
Designing A Portfolio Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir
Designing A Portfolio Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir
Research Collection School Of Computing and Information Systems
Algorithm portfolios seek to determine an effective set of algorithms that can be used within an algorithm selection framework to solve problems. A limited number of these portfolio studies focus on generating different versions of a target algorithm using different parameter configurations. In this paper, we employ a Design of Experiments (DOE) approach to determine a promising range of values for each parameter of an algorithm. These ranges are further processed to determine a portfolio of parameter configurations, which would be used within two online Algorithm Selection approaches for solving different instances of a given combinatorial optimization problem effectively. We …
Second Order-Response Surface Model For The Automated Parameter Tuning Problem, Aldy Gunawan, Hoong Chuin Lau
Second Order-Response Surface Model For The Automated Parameter Tuning Problem, Aldy Gunawan, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
Several automated parameter tuning procedures/configurators have been proposed in order to find the best parameter setting for a target algorithm. These configurators can generally be classified into model-free and model-based approaches. We introduce a recent approach which is based on the hybridization of both approaches. It combines the Design of Experiments (DOE) and Response Surface Methodology (RSM) with prevailing model-free techniques. DOE is mainly used for determining the importance of parameters. A First Order-RSM is initially employed to define the promising region for the important parameters. A Second Order-RSM is then built to approximate the center point as well as …
Traccs: Trajectory-Aware Coordinated Urban Crowd-Sourcing, Cen Chen, Shih-Fen Cheng, Aldy Gunawan, Archan Misra, Koustuv Dasgupta, Deepthi Chander
Traccs: Trajectory-Aware Coordinated Urban Crowd-Sourcing, Cen Chen, Shih-Fen Cheng, Aldy Gunawan, Archan Misra, Koustuv Dasgupta, Deepthi Chander
Research Collection School Of Computing and Information Systems
We investigate the problem of large-scale mobile crowd-tasking, where a large pool of citizen crowd-workers are used to perform a variety of location-specific urban logistics tasks. Current approaches to such mobile crowd-tasking are very decentralized: a crowd-tasking platform usually provides each worker a set of available tasks close to the worker's current location; each worker then independently chooses which tasks she wants to accept and perform. In contrast, we propose TRACCS, a more coordinated task assignment approach, where the crowd-tasking platform assigns a sequence of tasks to each worker, taking into account their expected location trajectory over a wider time …
Hippi Care Hospital: Towards Proactive Business Processes In Emergency Room Services, Kar Way Tan, Venky Shankaraman
Hippi Care Hospital: Towards Proactive Business Processes In Emergency Room Services, Kar Way Tan, Venky Shankaraman
Research Collection School Of Computing and Information Systems
It was 2.35 am on a Saturday morning. Wiki Lim, process specialist from the Process Innovation Centre (PIC) of Hippi Care Hospital (HCH), desperately doodling on her notepad for ideas to improve service delivery at HCH’s Emergency Department (ED). HCH has committed to the public that its ED would meet the service quality criterion of serving 90% of A3 and A4 patients, non-emergency patients with moderate to mild symptoms, within 90 minutes of their arrival at the ED. The ED was not able to meet this performance goal and Dr. Edward Kim, the head of the ED at HCH, had …
Multi-Agent Orienteering Problem With Time-Dependent Capacity Constraints, Cen Chen, Shih-Fen Cheng, Hoong Chuin Lau
Multi-Agent Orienteering Problem With Time-Dependent Capacity Constraints, Cen Chen, Shih-Fen Cheng, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
In this paper, we formulate and study the Multi-agent Orienteering Problem with Time-dependent Capacity Constraints (MOPTCC). MOPTCC is similar to the classical orienteering problem at single-agent level: given a limited time budget, an agent travels around the network and collects rewards by visiting different nodes, with the objective of maximizing the sum of his collected rewards. The most important feature we introduce in MOPTCC is the inclusion of multiple competing agents. All agents in MOPTCC are assumed to be self-interested, and they interact with each other when arrive at certain nodes simultaneously. As all nodes are capacitated, if a particular …
Diversity-Oriented Bi-Objective Hyper-Heuristics For Patrol Scheduling, Mustafa Misir, Hoong Chuin Lau
Diversity-Oriented Bi-Objective Hyper-Heuristics For Patrol Scheduling, Mustafa Misir, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
The patrol scheduling problem is concerned with assigning security teams to different stations for distinct time intervals while respecting a limited number of contractual constraints. The objective is to minimise the total distance travelled while maximising the coverage of the stations with respect to their security requirement levels. This paper introduces a hyper-heuristic strategy focusing on generating diverse solutions for a bi-objective patrol scheduling problem. While a variety of hyper-heuristics have been applied to a large suite of problem domains usually in the form of single-objective optimisation, we suggest an alternative approach for solving the patrol scheduling problem with two …
An Empirical Study Of Off-Line Configuration And On-Line Adaptation In Operator Selection, Zhi Yuan, Stephanus Daniel Handoko, Duc Thien Nguyen, Hoong Chuin Lau
An Empirical Study Of Off-Line Configuration And On-Line Adaptation In Operator Selection, Zhi Yuan, Stephanus Daniel Handoko, Duc Thien Nguyen, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
Automating the process of finding good parameter settings is important in the design of high-performing algorithms. These automatic processes can generally be categorized into off-line and on-line methods. Off-line configuration consists in learning and selecting the best setting in a training phase, and usually fixes it while solving an instance. On-line adaptation methods on the contrary vary the parameter setting adaptively during each algorithm run. In this work, we provide an empirical study of both approaches on the operator selection problem, explore the possibility of varying parameter value by a non-adaptive distribution tuned off-line, and incorporate the off-line with on-line …
Hybrid Metaheuristics For Solving The Quadratic Assignment Problem And The Generalized Quadratic Assignment Problem, Aldy Gunawan, Kien Ming Ng, Kim Leng Poh, Hoong Chuin Lau
Hybrid Metaheuristics For Solving The Quadratic Assignment Problem And The Generalized Quadratic Assignment Problem, Aldy Gunawan, Kien Ming Ng, Kim Leng Poh, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
This paper presents a hybrid metaheuristic for solving the Quadratic Assignment Problem (QAP). The proposed algorithm involves using the Greedy Randomized Adaptive Search Procedure (GRASP) to construct an initial solution, and then using a hybrid Simulated Annealing and Tabu Search (SA-TS) algorithm to further improve the solution. Experimental results show that the hybrid metaheuristic is able to obtain good quality solutions for QAPLIB test problems within reasonable computation time. The proposed algorithm is extended to solve the Generalized Quadratic Assignment Problem (GQAP), with an emphasis on modelling and solving a practical problem, namely an examination timetabling problem. We found that …
A Mathematical Model And Metaheuristics For Time Dependent Orienteering Problem, Aldy Gunawan, Zhi Yuan, Hoong Chuin Lau
A Mathematical Model And Metaheuristics For Time Dependent Orienteering Problem, Aldy Gunawan, Zhi Yuan, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
This paper presents a generalization of the Orienteering Problem, the Time-Dependent Orienteering Problem (TDOP) which is based on the real-life application of providing automatic tour guidance to a large leisure facility such as a theme park. In this problem, the travel time between two nodes depends on the time when the trip starts. We formulate the problem as an integer linear programming (ILP) model. We then develop various heuristics in a step by step fashion: greedy construction, local search and variable neighborhood descent, and two versions of iterated local search. The proposed metaheuristics were tested on modified benchmark instances, randomly …
Decentralized Stochastic Planning With Anonymity In Interactions, Pradeep Varakantham, Yossiri Adulyasak, Patrick Jaillet
Decentralized Stochastic Planning With Anonymity In Interactions, Pradeep Varakantham, Yossiri Adulyasak, Patrick Jaillet
Research Collection School Of Computing and Information Systems
In this paper, we solve cooperative decentralized stochastic planning problems, where the interactions between agents (specified using transition and reward functions) are dependent on the number of agents (and not on the identity of the individual agents) involved in the interaction. A collision of robots in a narrow corridor, defender teams coordinating patrol activities to secure a target, etc. are examples of such anonymous interactions. Formally, we consider problems that are a subset of the well known Decentralized MDP (DEC-MDP) model, where the anonymity in interactions is specified within the joint reward and transition functions. In this paper, not only …