Arrow Research search

Author name cluster

Mark Wallace 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers
1 author row

Possible papers

8

SoCS Conference 2024 Conference Paper

Efficient and Exact Public Transport Routing via a Transfer Connection Database

  • Abdallah Abu-Aisha
  • Mark Wallace 0001
  • Daniel Harabor
  • Bojie Shen

We explore the earliest arrival time problem in public transport journey planning. A journey typically consists of multiple scheduled public transport legs. The actual time required to transfer between these legs can substantially influence route planning. Therefore, we properly model transfers by incorporating their exact costs. We then introduce a novel oracle-based routing algorithm that constructs an efficient transfer database, considering the proposed transfer model. The database is leveraged online to quickly reconstruct the optimal journey in response to an earliest arrival time query. Our experimental results show that neglecting exact transfer costs often lead to either infeasible or suboptimal route plans. Furthermore, the findings highlight the efficiency of our algorithm in handling queries, demonstrated by response times within mere microseconds.

Details

SoCS Conference 2022 Conference Paper

Fast Traffic Assignment by Focusing on Changing Edge Flows (Extended Abstract)

  • Ali Davoodi
  • Mark Wallace 0001
  • Daniel Harabor

This paper presents a novel algorithm for solving the traffic assignment problem (TAP). Contrary to traditional algorithms, which use the one-to-all shortest path algorithm to solve the problem for all origin destinations (OD) pairs, this algorithm tracks the changes of the edges and (at certain iterations) solves the problem only for critical edges whose flows have changed substantially using a state-of-the-art edge p2p shortest path algorithm. When additionally, only OD pairs with larger flows are considered, this enhancement halves the time needed to optimize the solution with a very small error in a large-scale network.

Details

SoCS Conference 2021 Conference Paper

Customised Shortest Paths Using a Distributed Reverse Oracle

  • Arthur Mahéo
  • Shizhe Zhao
  • Hassan Afzaal
  • Daniel Harabor
  • Peter J. Stuckey
  • Mark Wallace 0001

We consider the design and implementation of a centralised oracle that provides commuters with customised and congestion-aware driving directions. Computing directions for a single journey is straightforward, but doing so at city-scale, in real-time, and under changing conditions is extremely challenging. In this work we describe a new type of centralised oracle which combines fast database-driven path planning with a query management system that distributes work across a small commodity cluster of networked machines. Our system allows large-scale changes to the underlying graph metric, from one query to the next, and it supports a variety of query types including optimal, bounded suboptimal, time-budgeted and k-prefix. Simulated experiments show strong results: we can provide real-time routing for all peak-hour commuter trips in the city of Melbourne, Australia.

Details

ICAPS Conference 2012 Conference Paper

CP and MIP Methods for Ship Scheduling with Time-Varying Draft

  • Elena Kelareva
  • Sebastian Brand
  • Philip Kilby
  • Sylvie Thiébaux
  • Mark Wallace 0001

Existing ship scheduling approaches either ignore constraints on ship draft (distance between the waterline and the keel), or model these in very simple ways, such as a constant draft limit that does not change with time. However, in most ports the draft restriction changes over time due to variation in environmental conditions. More accurate consideration of draft constraints would allow more cargo to be scheduled for transport on the same set of ships. We present constraint programming (CP) and mixed integer programming (MIP) models for the problem of scheduling ships at a port with time-varying draft constraints so as to optimise cargo throughput at the port. We also investigate the effect of several variations to the CP model, including a model containing sequence variables, and a model with ordered inputs. Our model allows us to solve realistic instances of the problem to optimality in a very short time, and produces better schedules than both scheduling with constant draft, and manual scheduling approaches used in practice at ports.

Details
v2026.09.13