Formulate OR model to reduce driver backtracking
Overview
This question evaluates skills in defining a quantitative driver-backtracking metric from GPS and assignment logs, detecting and validating backtracking segments, and formulating constrained optimization models for dispatch and repositioning, drawing on statistics, operations research, and stochastic optimization.
Define and reduce driver ‘backtracking’ in a marketplace. First, define a quantitative backtracking metric B per driver-hour from GPS and assignment logs, and describe an algorithm to detect backtracking segments and validate them with labels; then formulate an optimization model that assigns drivers to requests and repositioning tasks to minimize expected backtracking while meeting business goals (SLA on ETA, minimum utilization, zone fairness, cap on repositioning cost). State decision variables, objective, and constraints explicitly; choose a modeling approach (e.g., time-expanded network min-cost flow with penalties or a mixed-integer program) and discuss a real-time solution method (rolling horizon, column generation, Lagrangian relaxation) and approximation quality; finally, explain offline evaluation and an online experiment to validate improvements, and how to handle demand uncertainty via robust or stochastic optimization, including a toy three-zone, five-minute-interval example to illustrate constraints.