Customizable and Jointly Optimized Route Planning: A Deep Architecture Enabling Differentiable Shortest-Path Search

# Customizable and Jointly Optimized Route Planning: A Deep Architecture Enabling Differentiable Shortest-Path Search
Source: [https://arxiv.org/html/2609.19996](https://arxiv.org/html/2609.19996)
,Chao ChenAffiliation:Alibaba Group,Beijing,Chinaemail:[cc201598@alibaba\-inc\.com](mailto:[email protected]),Longfei XuAffiliation:Alibaba Group,Beijing,Chinaemail:[longfei\.xl@alibaba\-inc\.com](mailto:[email protected]),Chenguang JiNote:Corresponding author\.Affiliation:Alibaba Group,Beijing,Chinaemail:[chenguang\.jcg@alibaba\-inc\.com](mailto:[email protected]),Hengbin CuiAffiliation:Alibaba Group,Hangzhou,Chinaemail:[alexcui\.chb@alibaba\-inc\.com](mailto:[email protected]),Kaikui LiuAffiliation:Alibaba Group,Beijing,Chinaemail:[damon@alibaba\-inc\.com](mailto:[email protected])andXiaolong LiAffiliation:Alibaba Group,Hangzhou,Chinaemail:[xl\.li@alibaba\-inc\.com](mailto:[email protected])

###### Abstract\.

With the widespread use of online navigation and ride\-hailing services, achieving optimal route planning for diverse user preferences has recently attracted increasing attention\. Classic graph algorithms for pathfinding use heuristic cost functions to define edge weight, thus providing no optimality guarantee of route quality\. Prior data\-driven approaches equating ground truth of the optimal route with user trajectory, which is however moderately influenced by the navigation service, suffers from the feedback loop problem\. To address these issues, we propose a deep architecture that is able to jointly optimize cost functions and route\-ranking model towards any route preference\. First, we run a multi\-objective Dijkstra algorithm offline to collect the set of Pareto optimal routes, deeming it as the complete candidate set\. Exploiting the property of such a set, we design a neural network structure that emulates shortest\-path search and route ranking in an end\-to\-end differentiable manner\. Second, we define route preference as a task of constrained optimization of route attributes, and propose a novel loss function that optimizes a single\-objective variable, with other variables strictly under constraints\. We conduct extensive experiments on real\-world datasets\. The results show that our architecture significantly outperforms state\-of\-the\-art methods in route quality and customizability\.

###### Keywords:

route planning, shortest\-path algorithm, deep neural networks, multi\-objective optimization, constrained optimization

## 1\.Introduction

Route planning aims to find the optimal path between two locations\. It has widespread applications in modern industry and plays an especially crucial role in high\-tech fields, such as real\-time GPS navigation in map apps, on\-demand ride\-hailing service, intelligent logistics transportation systems, etc\. Performance of route planning delivers significant social and economic impacts in daily life\.

Challenges in real\-world route planning lie in two aspects\. First, given an origin\-destination pair \(OD pair\), there are infinite possible routes in\-between, and the ones recalled hinge on a set of cost functions \(a mapping from an edge in a graph to a real\-valued weight\), which are usually predetermined heuristically\([Bast et al\., 2016](https://arxiv.org/html/2609.19996#bib.bib13)\)and thus have no optimality guarantee\. One way to get around this issue is to use multi\-objective routing\([Martins, 1984](https://arxiv.org/html/2609.19996#bib.bib5)\)\. In multi\-objective optimization\([Marler and Arora, 2004](https://arxiv.org/html/2609.19996#bib.bib14)\), a solution is called Pareto optimal if none of the objective functions can be improved in value without degrading some of the other objective values\. Therefore, a Pareto\-optimal route set can be deemed as a complete candidate set, as the full commodity set in e\-commerce, in that it contains the optimal solution for any route preference built upon these objectives\. The idea is illustrated in Figure[1](https://arxiv.org/html/2609.19996#S1.F1)\. However, multi\-objective routing is not polynomially solvable and thus cannot be applied in real\-time services\. Second, provided that users of navigation apps tend to follow the recommended \(top\-ranked\) route, user trajectories are often biased with respect to their true preference\. As a consequence, prior formalism\([Wang et al\., 2019](https://arxiv.org/html/2609.19996#bib.bib3)\)that uses user trajectory as the supervising signal suffers from the feedback loop problem\([Sinha et al\., 2017](https://arxiv.org/html/2609.19996#bib.bib9)\)and neglects to construct a rigorous definition for route preference, and is thus unable to customize route planning as needed\.

Figure 1\.Comparison of routes recalled with single\-objective Dijkstra \(left\) and multi\-objective Dijkstra \(right\)\.![Refer to caption](https://arxiv.org/html/2609.19996v1/pareto_recall_case_a_gray.png)
![Refer to caption](https://arxiv.org/html/2609.19996v1/pareto_recall_case_d_gray.png)

To solve the first issue, we propose an end\-to\-end learning framework consisting of a differentiable shortest\-path search module and a following route\-ranking module\. In real\-world route planning, though many possible routes exist between an OD pair, only a few of them are practical to users\. Inspired by this observation, we design a differentiable shortest\-path search structure to learn several cost functions, whose shortest paths constitute a condensed version of the Pareto\-optimal set that suffices to meet user demands\. Specifically, we first run the multi\-objective Dijkstra algorithm offline to collect the Pareto\-optimal set for each routing request \(OD pair\)\. Adopting linear combination of these objectives as the learnable cost function \(scoring metrics\), we then transfer the shortest\-path problem into an equivalent ranking problem: the lowest\-scoring route in the Pareto\-optimal set is theoretically guaranteed to be the shortest route under the scoring metrics\. As such, a soft indicator vector of the recalled routes is constructed using the learnable weights of the cost functions\. At last, the ranking module takes as input the indicator\-multiplied route features and produces the ranking score\.

To solve the second issue, we propose a formal definition for route preference, which is immune to the position bias\. In daily experience, users’ route preference could be usually phrased in a format describing a constrained optimization task\. For example, “avoid congestion” may mean “prefer a route with the least congestion as long as its travel time and distance are no more than 1\.2 times the minimum values”\. This motivates us to equate each route preference as a customized loss function, with a single\-objective function and a few constraints\. Moreover, since route attribute, such as travel time, is innately independent of the ranking strategy, there exists an unbiased estimator trainable on user trajectories for each attribute\. We build these estimators and apply them to construct the objective function and constraints, naturally avoiding the feedback loop problem\.

To further suit the above\-mentioned constraints for practical application, we propose a novel batch sampling method\. In industrial navigation services, routing requests with disparate parameters correspond to different travel scenarios\. For instance, a request with 10 km OD\-distance issued at peak hour is likely a daily commute, while another request with 5 km distance at night might be a casual shopping trip\. Therefore, the constraints must be enforced locally across the parametric space of requests to avoid severely damaging the routing performance on a certain portion of requests\. To serve this purpose, we use a two\-stage batch sampling method in each iteration: first, randomly sample an anchor point in the parametric space, and then randomly sample a batch of requests within a window centered around the anchor as the training data\.

In this paper, we propose an end\-to\-end machine learning solution for route planning that overcomes the drawbacks of the existing methods\. We build a module to find the shortest path in a differentiable manner\. In this module, the Pareto\-optimal set are collected offline via a multi\-objective Dijkstra algorithm\. Using linear combinations of these objectives as the learnable cost functions, we transform shortest\-path search into an equivalent ranking problem within the Pareto\-optimal set\. We design a deep neural network structure to emulate such a process and produce a soft\-indicator vector of the associated shortest routes\. The following rank module applies the same indicator technique to further extract the top\-ranked route and feed its attributes into the loss function\. Particularly, the loss function is customized in line with the route preference, with an objective function and a few constraints\. Variables in the loss function, which represent route attributes, are predicted with estimators inferred from historical user trajectories\. This architecture offers several advantages\. First, the learned cost functions are guaranteed to be optimal towards the route preference\. Second, it is computationally fast enough to be applied in real\-time services\. Third, it gets rid of the problem of position bias, and can be customized to adapt to any route preference\. The results of city\-scale online A/B testing and offline evaluation demonstrate that the proposed solution outperforms state\-of\-the\-art methods in both route quality and customizability\.

The contribution of this paper can be summarized as follows:

- •We propose a novel end\-to\-end learning framework for route planning, which is able to jointly optimize the cost functions and route\-ranking model\.
- •We define route preference as a constrained optimization task, embodied in a customizable loss function\.
- •We propose a novel batch sampling method to enforce local constraints in a machine learning task\.
- •We evaluate our proposed solution with city\-scale online A/B testing and offline data from Amap\.111Amap is the top\-tier LBS\-service provider in China, and served more than 150 million users on the National Day of the People’s Republic of China in 2020, according to a third\-party report https://www\.questmobile\.com\.cn/en\.The results show that the proposed framework significantly outperforms state\-of\-the\-art methods in both route quality and customizability\.

The rest of the paper is organized as follows: Section[2](https://arxiv.org/html/2609.19996#S2)reviews the related works\. Section[3](https://arxiv.org/html/2609.19996#S3)outlines the preliminary concepts and formulates the joint optimization problem of route planning\. Section[4](https://arxiv.org/html/2609.19996#S4)details the structure of the proposed learning framework\. Section[5](https://arxiv.org/html/2609.19996#S5)describes the results of the experiment\. Finally, Section[6](https://arxiv.org/html/2609.19996#S6)concludes the paper\.

## 2\.RELATED WORK

Our work is related to the following research directions:

Graph Algorithms for Optimal Path Finding\.Route planning has been studied for decades\. In the early days, the core issue was to speed up the shortest\-path finding for real\-world application\([Bast et al\., 2016](https://arxiv.org/html/2609.19996#bib.bib13)\)\. Goal\-directed techniques, such as A star\([Hart et al\., 1968](https://arxiv.org/html/2609.19996#bib.bib6)\), ALT\([Goldberg and Harrelson, 2005](https://arxiv.org/html/2609.19996#bib.bib7)\), etc\. tactically guide the search toward the target and obtain a considerable acceleration\. Contraction hierarchy\([Geisberger et al\., 2012](https://arxiv.org/html/2609.19996#bib.bib11)\)and customizable route planning \(CRP\)\([Delling et al\., 2017](https://arxiv.org/html/2609.19996#bib.bib8)\)—the preprocessing\-based methods—compute reusable shortcuts in advance and further achieve milliseconds of query response time on continental\-scale road networks\. These approaches, though compatible with any common metrics, such as distance, discuss little about how to optimize the cost function\. To overcome this limitation, instead of a single optimal route, multi\-objective routing\([Martins, 1984](https://arxiv.org/html/2609.19996#bib.bib5);[Delling et al\., 2015](https://arxiv.org/html/2609.19996#bib.bib15)\)computes the Pareto\-optimal set that offers the best achievable route diversity with respect to the objectives\. Multi\-objective routing has been successfully deployed in public\-transit routing\([Delling et al\., 2015](https://arxiv.org/html/2609.19996#bib.bib15)\)\. Nonetheless, this routing approach is infeasible for larger road networks, due to its exponential time complexity\.

Personalized Route Planning\.Assuming historical trajectories fully reveal users’ route preferences, prior works either develop algorithms to directly search the most frequently travelled patterns\([Luo et al\., 2013](https://arxiv.org/html/2609.19996#bib.bib2)\), or utilize machine learning techniques to capture users’ transition probability between locations\([Wang et al\., 2019](https://arxiv.org/html/2609.19996#bib.bib3)\)\. However, this basic assumption contradicts on\-the\-ground realities: \(1\) over 95% of online\-navigation users follow the recommended \(top\-ranked\) route, and their behaviors are thereby moderately influenced by the routing strategy of the map app; \(2\) users tend to drive the familiar route, which is not necessarily in their best interest\.

Recommender System\.Recommender systems have long been deployed in e\-commence\([Schafer et al\., 2001](https://arxiv.org/html/2609.19996#bib.bib10)\), video\-sharing platforms\([Zhao et al\., 2019](https://arxiv.org/html/2609.19996#bib.bib12)\), etc\. With finite candidate items, prior approaches primarily focus on optimizing the ranking model\. To reconcile conflicting objectives, such as clicks, watches, likes and dismissals on video\-sharing platforms,[Zhao et al\. \(2019\)](https://arxiv.org/html/2609.19996#bib.bib12)propose a multi\-task architecture, that makes a prediction for each objective and adopts as the loss a combined score using a combination function in the form of weighted multiplication\. However, lacking the capability to constrain individual objectives, such a loss function may improve the combined score at the expense of severely jeopardizing some objectives, which is unacceptable for navigation service\.

Deep Learning for Combinatorial Optimization\.Deep learning has shown promising potential for solving combinatorial optimization problems\. In\([Vinyals et al\., 2015](https://arxiv.org/html/2609.19996#bib.bib4)\), pointer network is proposed to learn approximate solutions to the travelling salesman problem\. However, no feasible data\-driven solution has been proposed so far to tackle the multi\-objective routing problem in city\-wide road networks\.

## 3\.PRELIMINARIES

In this section, we provide key definitions, and outline the joint optimization problem of route planning\.

Road Network\. A road network is a directed graphG=\(V,E\)G=\(V,E\), whereVVis a vertex set andEEis an edge set\. Each edgee∈Ee\\in Eis denoted by an ordered pair of vertices\(u,v\)∈V×V\(u,v\)\\in V\\times V\. In particular, an edge could either refer to a road segment or a turn at intersection\.

Route\.Given a routing requestq=\(eoCLOSEq=\(e\_\{o\},OPENed\)e\_\{d\}\), a routeppbetween the pair is a sequence of edges\{eo=e1,e2,e3,…,eN−1,eN=ed\}\\\{e\_\{o\}=e\_\{1\},e\_\{2\},e\_\{3\},\\ldots,e\_\{N\-1\},e\_\{N\}=e\_\{d\}\\\}, whereei,ei\+1,∀i∈\[1,N−1\]e\_\{i\},e\_\{i\+1\},\\forall i\\in\[1,N\-1\]are adjacent in the graph\.

Route and Edge Attribute\.While most of route attributes are directly available from basic map data, such as distance, number of traffic lights, toll, etc\., some attributes—for instance, deviation rate and travel time—are unknown in advance and thus need prediction\. We build a separate estimator for each of these attributes\. Letck,1≤k≤Kc^\{k\},1\\leq k\\leq Kbe all the route attributes considered in this work, andcpk∈ℝ≥0c\_\{p\}^\{k\}\\in\\mathbb\{R\}\_\{\\geq 0\}refer to thekkth attribute value of routepp\. A similar convention holds for edges:cek,e∈Ec\_\{e\}^\{k\},e\\in Eis just the edge weight\.

Pareto Set\.Given an OD pairqq, letXqX\_\{q\}be the set of all legitimate routes ofqq\. Letx,y∈Xqx,y\\in X\_\{q\}be two distinct routes\.xxdominatesyyif and only ifcxk≤cykc\_\{x\}^\{k\}\\leq c\_\{y\}^\{k\}holds for allk∈\{1,…,K\}k\\in\\\{1,\\ldots,K\\\}and the strict inequality holds at least once\. LetXqD=\{x∈Xq\|∃y∈Xq​such that​y​dominates​x\}X\_\{q\}^\{D\}=\\\{x\\in X\_\{q\}\\,\|\\,\\exists y\\in X\_\{q\}\\,\\text\{such that\}\\,y\\,\\text\{dominates\}\\,x\\\}be the set of dominated routes\. ThenXqP=Xq−XqDX\_\{q\}^\{P\}=X\_\{q\}\-X\_\{q\}^\{D\}is the set of non\-dominated routes, or the Pareto\-optimal routes\. We callXqPX\_\{q\}^\{P\}the Pareto set ofqq\.

Multi\-Objective Routing \(MOR\)\.MOR recalls the Pareto set with respect to given objectives\. Let𝒄MOR=\(co1,co2,…,coJ\)\\boldsymbol\{c^\{\\text\{MOR\}\}\}=\(c^\{o\_\{1\}\},c^\{o\_\{2\}\},\\ldots,c^\{o\_\{J\}\}\)denote theJJobjectives of MOR used in this paper\.

Cost Function\.A cost functionf:E→ℝ≥0f:E\\to\\mathbb\{R\}\_\{\\geq 0\}maps an edgee∈Ee\\in Eto a non\-negative real valuec∈ℝ≥0c\\in\\mathbb\{R\}\_\{\\geq 0\}\. Given an OD pairqq, the cost function uniquely defines the shortest path ofqqin its own metrics\. We use cost function and metrics interchangeably in the rest of the paper\.

Route Preference\.We formalize route preference𝒫\\mathscr\{P\}as a task of constrained optimization

\(1\)𝒫\\displaystyle\\mathscr\{P\}=\{h0,\(h1,h2,…,hL\),\(b1,b2,…,bL\)\}\\displaystyle=\\\{h^\{0\},\\\>\(h^\{1\},h^\{2\},\\ldots,h^\{L\}\),\\\>\(b^\{1\},b^\{2\},\\ldots,b^\{L\}\)\\\}wherehl∈\{c1,c2,…,cK\},bl∈ℝh^\{l\}\\in\\\{c^\{1\},c^\{2\},\\ldots,c^\{K\}\\\},\\,b^\{l\}\\in\\mathbb\{R\},h0h^\{0\}denotes the objective attribute,hl,bl,1≤l≤Lh^\{l\},b^\{l\},1\\leq l\\leq Ldenotes the constrained attributes and associated thresholds\. To facilitate the following description, we use an index converter𝒞\\mathscr\{C\}to describe the correspondence betweenhhandcc—that is,hl=c𝒞⁡\(l\)h^\{l\}=c^\{\\mathscr\{C\}\(l\)\}\.

Joint Optimization Problem of Route Planning\.Like classic recommender systems, route planning is an item\-retrieval process with both a recall and a ranking stage\. Specifically, provided a set of cost functionsF=\{f1,f2,…,fM\}F=\\\{f\_\{1\},f\_\{2\},\\ldots,f\_\{M\}\\\}and a routing requestqq, the recall moduleRRruns pathfinding algorithms to retrieve the pathsR⁡\(q\)=\{p1,p2,…,pM′\}⊂XqR\(q\)=\\\{p\_\{1\},p\_\{2\},\\ldots,p\_\{M^\{\\prime\}\}\\\}\\subset X\_\{q\}\. A scoring functiong:Xq→ℝg:X\_\{q\}\\to\\mathbb\{R\}scores each path, and the highest\-rated onepopt​\(q\)=argmaxp∈R⁡\(q\)g​\(p\)p\_\{\\text\{opt\}\}\(q\)=\\argmax\_\{p\\in R\(q\)\}g\(p\)is recommended to the user\. LetQQdenote a set of requests\. Given a route preference𝒫\\mathscr\{P\}, we formalize the joint optimization problem of route planning as

\(2\)minF,g\\displaystyle\\min\_\{F,g\}\\,1\|Q\|​∑q∈Qhpopt​\(q\)0\\displaystyle\\frac\{1\}\{\|Q\|\}\\sum\\limits\_\{q\\in Q\}h^\{0\}\_\{\{p\_\{\\text\{opt\}\}\(q\)\}\}\(3\)s\.t\.\\displaystyle s\.t\.\\quad1\|Q\|∑q∈Qhlpopt​\(q\)≤bl,l=1,…,L\\displaystyle\\frac\{1\}\{\|Q\|\}\\sum\\limits\_\{q\\in Q\}h^\{l\}\_\{\{p\_\{\\text\{opt\}\}\(q\)\}\}\\leq b^\{l\},\\quad l=1,\\ldots,LwhereF,gF,gare learnable functions\.

## 4\.METHODOLOGY

### 4\.1\.Overall Architecture

In this section, we describe the overall architecture of the learning framework, as illustrated in Figure[2](https://arxiv.org/html/2609.19996#S4.F2)\.

We first run pathfinding algorithms to generate the candidate routes for each request \(module 1\)\. Specifically, we apply CRP with the heuristic cost functions to retrieve the route setXHX^\{H\}\(heuristic route set\), and multi\-objective Dijkstra \(MOD\) to retrieve the Pareto setXPX^\{P\}\. Using the attribute estimators inferred from historical trajectories, we transformXH,XPX^\{H\},X^\{P\}into the feature matricesH\|XH\|×K,P\|XP\|×KH\_\{\|X^\{H\}\|\\times K\},P\_\{\|X^\{P\}\|\\times K\}\.

To learn the cost functions inFF, we design module 2 to emulate shortest\-path finding in a differentiable manner\. First, we set allffto be linear combinations of theJJobjectives used in MOD—that is,fi​\(e\)=𝒄eMOR⋅𝒘iT,e∈Ef\_\{i\}\(e\)=\\boldsymbol\{c\}\_\{e\}^\{\\text\{MOR\}\}\\cdot\\boldsymbol\{w\}\_\{i\}^\{T\},e\\in E\. We then extract a submatrixG\|XP\|×JG\_\{\|X^\{P\}\|\\times J\}fromPPwith columns of𝒄MOR\\boldsymbol\{c\}^\{\\text\{MOR\}\}\. Next, we multiplyGGbyWJ×ML=\[𝒘1,𝒘2,…,𝒘M\]W^\{L\}\_\{J\\times M\}=\[\\boldsymbol\{w\}\_\{1\},\\boldsymbol\{w\}\_\{2\},\.\.\.,\\boldsymbol\{w\}\_\{M\}\], the weight matrix ofFF, to obtain route costs under every metrics\. At last, by applying softmax over the route dimension \(rows\) and max pooling over the metrics dimension \(columns\), we obtain a soft indicator vectorI\|XP\|I\_\{\|X^\{P\}\|\}of the routes recallable withFF\.

In module 3, we use MLP to score each route, and apply again the indicator technique to approximately pick up the feature vector of the top\-rated route\. This vector is fed into a loss function customized in line with the preference𝒫\\mathscr\{P\}, generating the supervising signal\.

We elaborate each of the modules in subsequent sections\.

![Refer to caption](https://arxiv.org/html/2609.19996v1/big_figure.png)Figure 2\.The flowchart of the overall architecture\.
### 4\.2\.Amap’s Route\-planning System

To compute the shortest path, Amap uses the customizable route\-planning algorithm \(CRP\)\([Delling et al\., 2017](https://arxiv.org/html/2609.19996#bib.bib8)\)\. To be specific, CRP has a two\-stage preprocessing phase and a query phase\. The road network is first partitioned into a few nested levels of cells with a minimum number of boundary \(cross\-cell\) edges \(metrics\-independent stage\)\. The cost of shortest path between every pair of boundary edges \(called a “shortcut”\) is next computed within each cell \(metrics\-dependent stage\)\. Exploiting high\-level shortcuts, the query algorithm takes much less steps to find the optimal route, resulting in two to three orders of magnitude of speed\-up compared to plain Dijkstra\. To further acquire alternative routes\([Abraham et al\., 2010](https://arxiv.org/html/2609.19996#bib.bib16)\), we use a bi\-directional search in the query phase, which does not terminate until sufficient vertices have been doubly scanned \(called “via vertex”\)\. For every via vertex, the concatenation of the shortest paths origin\-to\-via\-vertex and via\-vertex\-to\-destination uniquely defines an alternative route\.

Amap has several heuristic cost functions in\-service\. Depending on the route option, one or many of them are utilized to recall routes\. In our experiment, we use two heuristic cost functions: “fastest in the free\-flow period” and “avoid congestion”, as detailed in Table[6](https://arxiv.org/html/2609.19996#S5.T6)\.

### 4\.3\.Multi\-Objective Routing and the Pareto Set

As far as the objectives are concerned, the Pareto set is considered to include all valuable routes, therefore representing an upper bound achievable for a route recall system\. We use as the objectives the five attributes that are most commonly concerned by digital map users: the distance, the live travel time, the toll, the number of traffic lights, and the number of driving maneuvers \(turns\)\. To compute the Pareto setXPX^\{P\}, we exploit the multi\-objective Dijkstra algorithm\([Delling et al\., 2015](https://arxiv.org/html/2609.19996#bib.bib15)\), which has an exponential time complexity\.

### 4\.4\.Feature Matrices of Candidate Routes

In this work, two route attributes need prediction: the travel time and the deviation rate\. To predict each attribute, we train a separate estimator with historical user trajectories\. Specifics of the estimators are as follows:

- •Estimated time of arrival \(ETA\): Using real travel time as a label, we train a regression model with MSE loss to predict the travel time of any given route\.
- •Deviation rate estimator: Deviation rate is a categorical variable with two values: 1 if the user deviates from the top\-ranked route, and 0 otherwise\. We train a binary classifier to predict the deviation probability of any given route\.

Using the above estimators, we obtain the feature matricesH∈ℝ≥0\|XH\|×K,P∈ℝ≥0\|XP\|×KH\\in\\mathbb\{R\}\_\{\\geq 0\}^\{\|X^\{H\}\|\\times K\},P\\in\\mathbb\{R\}\_\{\\geq 0\}^\{\|X^\{P\}\|\\times K\}for the heuristic set and the Pareto set\.

To prevent numerical issues and to ensure convergence, we perform the normalization onH,PH,Pas follows: Given a matrixX∈ℝM×NX\\in\\mathbb\{R\}^\{M\\times N\}, letxjmax=max1≤i≤M⁡xi​jx\_\{j\}^\{\\text\{max\}\}=\\max\_\{1\\leq i\\leq M\}x\_\{ij\}\. We transformxi​jx\_\{ij\}into\(xjmax−xi​j\+1\)xvmax\\frac\{\(x\_\{j\}^\{\\text\{max\}\}\-x\_\{ij\}\+1\)\}\{x\_\{v\}^\{\\text\{max\}\}\}, wherevvis a fixed index that corresponds to a feature with the largest numerical magnitude—distance in this paper\.

### 4\.5\.Differentiable Shortest Path Search

We set allffto be the weighted sum of the objectives used in MOD\. Such a formulation not only eases the interpretation but also makes it possible to emulate shortest\-path finding in a differentiable manner, as stated by the following theorem:

Theorem 1\.GivenJJobjectives𝒄=\(co1,co2,…,coJ\)\\boldsymbol\{c\}=\(c^\{o\_\{1\}\},c^\{o\_\{2\}\},\\dots,c^\{o\_\{J\}\}\)and an OD pairqq, letXqPX\_\{q\}^\{P\}denote the Pareto set with respect to𝒄\\boldsymbol\{c\}\. For an arbitrary weight vector𝒘∈ℝ\>01×J\\boldsymbol\{w\}\\in\\mathbb\{R\}\_\{\>0\}^\{1\\times J\}, the linear cost functionf⁡\(e\)=𝒄e⋅𝒘f\(e\)=\\boldsymbol\{c\}\_\{e\}\\cdot\\boldsymbol\{w\}recalls the shortest pathp0∈XqP,p0=argminp∈XqP𝒄p⋅𝒘p\_\{0\}\\in X\_\{q\}^\{P\},p\_\{0\}=\\argmin\_\{p\\in X\_\{q\}^\{P\}\}\\boldsymbol\{c\}\_\{p\}\\cdot\\boldsymbol\{w\}\.

Proof\.LetXqDX\_\{q\}^\{D\}denote the set of dominated routes, andXq=XqP∪XqDX\_\{q\}=X\_\{q\}^\{P\}\\cup X\_\{q\}^\{D\}\. Given an arbitrary routep′∈Xqp^\{\\prime\}\\in X\_\{q\}, ifp′∈XqPp^\{\\prime\}\\in X\_\{q\}^\{P\}, then𝒄p0⋅𝒘=minp∈XqP⁡𝒄p⋅𝒘≤𝒄p′⋅𝒘\\boldsymbol\{c\}\_\{p\_\{0\}\}\\cdot\\boldsymbol\{w\}=\\min\_\{p\\in X\_\{q\}^\{P\}\}\\boldsymbol\{c\}\_\{p\}\\cdot\\boldsymbol\{w\}\\leq\\boldsymbol\{c\}\_\{p^\{\\prime\}\}\\cdot\\boldsymbol\{w\}, concluding the proof\. Otherwise,p′∈XqDp^\{\\prime\}\\in X\_\{q\}^\{D\}\. So there must exist a routep′′∈XqPp^\{\\prime\\prime\}\\in X\_\{q\}^\{P\}which dominatesp′p^\{\\prime\}—that is,cp′′k≤cp′kc\_\{p^\{\\prime\\prime\}\}^\{k\}\\leq c\_\{p^\{\\prime\}\}^\{k\}holds for allk∈\{1,…,K\}k\\in\\\{1,\\ldots,K\\\}and the strict inequality holds at least once\. Clearly,𝒄p′′⋅𝒘−𝒄p′⋅𝒘=∑1≤k≤K\(cp′′k−cp′k\)​wk<0\\boldsymbol\{c\}\_\{p\_\{\\prime\\prime\}\}\\cdot\\boldsymbol\{w\}\-\\boldsymbol\{c\}\_\{p\_\{\\prime\}\}\\cdot\\boldsymbol\{w\}=\\sum\_\{1\\leq k\\leq K\}\(c\_\{p^\{\\prime\\prime\}\}^\{k\}\-c\_\{p^\{\\prime\}\}^\{k\}\)w\_\{k\}<0\. Therefore,𝒄p0⋅𝒘=minp∈XqP⁡𝒄p⋅𝒘≤𝒄p′′⋅𝒘<𝒄p′⋅𝒘\\boldsymbol\{c\}\_\{p\_\{0\}\}\\cdot\\boldsymbol\{w\}=\\min\_\{p\\in X\_\{q\}^\{P\}\}\\boldsymbol\{c\}\_\{p\}\\cdot\\boldsymbol\{w\}\\leq\\boldsymbol\{c\}\_\{p^\{\\prime\\prime\}\}\\cdot\\boldsymbol\{w\}<\\boldsymbol\{c\}\_\{p^\{\\prime\}\}\\cdot\\boldsymbol\{w\}\. The proof is concluded\.

According to Theorem 1, finding the shortest path of a cost function is equivalent to sorting the Pareto set by the same metrics\. Following this idea, we first extract a submatrixG∈ℝ\|XP\|×JG\\in\\mathbb\{R\}^\{\|X^\{P\}\|\\times J\}fromPPwith columns of𝒄MOR\\boldsymbol\{c\}^\{\\text\{MOR\}\}—that is,Gi​j=Pi​ojG\_\{ij\}=P\_\{io\_\{j\}\}\. LetWL∈ℝJ×MW^\{L\}\\in\\mathbb\{R\}^\{J\\times M\}denote the matrix representation ofFF, with thejjth column representing the weight vector infj∈Ff\_\{j\}\\in F, andS∈ℝ\|XP\|×M=G×WLS\\in\\mathbb\{R\}^\{\|X^\{P\}\|\\times M\}=G\\times W^\{L\}\.Si​jS\_\{ij\}is the cost of routeiiwith respect tofjf\_\{j\}\. To identify the shortest route for each cost function, we apply softmax onSSover the rows and obtain the soft indicator matrixS′∈ℝ\|XP\|×MS^\{\\prime\}\\in\\mathbb\{R\}^\{\|X^\{P\}\|\\times M\}

\(4\)Si​j′\\displaystyle S\_\{ij\}^\{\\prime\}=eSi​j/τ1∑1≤k≤\|XP\|eSk​j/τ1,1≤i≤\|XP\|,1≤j≤M\\displaystyle=\\dfrac\{e^\{S\_\{ij\}/\\tau\_\{1\}\}\}\{\\sum\\limits\_\{1\\leq k\\leq\|X^\{P\}\|\}e^\{S\_\{kj\}/\\tau\_\{1\}\}\},\\quad 1\\leq i\\leq\|X^\{P\}\|,1\\leq j\\leq Mwhere the value of the shortest route in each metrics can vary from1\|XP\|\\frac\{1\}\{\|X^\{P\}\|\}to unity, depending on the tunable scaling factorτ1\\tau\_\{1\}\. Since different cost functions may recall the same shortest route, we apply max pooling onS′S^\{\\prime\}over the columns \(metrics dimension\) to remove duplicates, obtaining a soft indicator vector𝒔′′∈ℝ\|XP\|\\boldsymbol\{s\}^\{\\prime\\prime\}\\in\\mathbb\{R\}^\{\|X^\{P\}\|\}:

\(5\)si′′=max1≤j≤M⁡Si​j′,1≤i≤\|XP\|\\displaystyle s\_\{i\}^\{\\prime\\prime\}=\\max\_\{1\\leq j\\leq M\}\{S\_\{ij\}^\{\\prime\}\},\\quad 1\\leq i\\leq\|X^\{P\}\|

### 4\.6\.Ranking Module

Input of the ranking module is a concatenation of two route\-feature matrices,U=\[HP′\]U=\\left\[\\begin\{smallmatrix\}H\\\\ P^\{\\prime\}\\end\{smallmatrix\}\\right\], whereHHcorresponds to the heuristic routes, andP′P^\{\\prime\}corresponds to the routes recalled withFF\. To obtainP′P^\{\\prime\}, we approximately zero the rows inPPassociated with the non\-recallable routes ofFF, using the previous soft indicator vector:

\(6\)Pi​j′=Pi​j×si′′,1≤i≤\|XP\|,1≤j≤M\\displaystyle P\_\{ij\}^\{\\prime\}=P\_\{ij\}\\times s\_\{i\}^\{\\prime\\prime\},\\quad 1\\leq i\\leq\|X^\{P\}\|,1\\leq j\\leq M
Next, we use a multi\-layer perceptron \(MLP\) to score each route and generate the rating vector𝒗\\boldsymbol\{v\}withvi=MLP​\(𝒖i\)v\_\{i\}=\\text\{MLP\}\(\\boldsymbol\{u\}\_\{i\}\), where𝒖i∈ℝK\\boldsymbol\{u\}\_\{i\}\\in\\mathbb\{R\}^\{K\}is theiith row ofUU\. By applying softmax on𝒗\\boldsymbol\{v\}, we further acquire a soft indicator vector𝒕∈ℝ1×\(\|XH\|\+\|XP\|\)\\boldsymbol\{t\}\\in\\mathbb\{R\}^\{1\\times\(\|X^\{H\}\|\+\|X^\{P\}\|\)\}of the top\-ranked route:

\(7\)ti=evi/τ2∑1≤i≤\|XH\|\+\|XP\|evi/τ2\\displaystyle t\_\{i\}=\\dfrac\{e^\{v\_\{i\}/\\tau\_\{2\}\}\}\{\\sum\\limits\_\{1\\leq i\\leq\|X^\{H\}\|\+\|X^\{P\}\|\}\{e^\{v\_\{i\}/\\tau\_\{2\}\}\}\}At last, we obtain the attribute vector of the top\-ranked route in two forms:

- •Approximate form𝒂∈ℝ1×K\\boldsymbol\{a\}\\in\\mathbb\{R\}^\{1\\times K\}:𝒂=𝒕×U\\boldsymbol\{a\}=\\boldsymbol\{t\}\\times U\.
- •Exact form𝒂′∈ℝ1×K\\boldsymbol\{a\}^\{\\prime\}\\in\\mathbb\{R\}^\{1\\times K\}:𝒂′\\boldsymbol\{a\}^\{\\prime\}is theiopti\_\{\\text\{opt\}\}th row of\[HP\]\\left\[\\begin\{smallmatrix\}H\\\\ P\\end\{smallmatrix\}\\right\], whereiopt=argmax1≤i≤\|XH\|\+\|XP\|tii\_\{\\text\{opt\}\}=\\argmax\_\{1\\leq i\\leq\|X^\{H\}\|\+\|X^\{P\}\|\}t\_\{i\}\.

### 4\.7\.Model Training

Local Constraints\.Section[3](https://arxiv.org/html/2609.19996#S3)gives the formulation of route preference: an objective attribute plus a set of constrained attributes with thresholds\. To avoid badcases, we further enforce the constraints to be locally valid across a three\-dimensional parametric space of routing requestℤ=𝔻×𝕋×𝕎\\mathbb\{Z\}=\\mathbb\{D\}\\times\\mathbb\{T\}\\times\\mathbb\{W\}, whered∈𝔻=ℝ\>0d\\in\\mathbb\{D\}=\\mathbb\{R\}\_\{\>0\}denotes the great\-circle distance of the OD pair,t∈𝕋=\{t∈ℕ\|0≤t<24\}t\\in\\mathbb\{T\}=\\\{t\\in\\mathbb\{N\}\\,\|\\,0\\leq t<24\\\}denotes the hour index of the request time, and𝕎=\{w​e​e​k​d​a​y,w​e​e​k​e​n​d\}\\mathbb\{W\}=\\\{weekday,weekend\\\}denotes the weekday/weekend attribute of the request time\. To be precise, the constraints hold in any continuous subspace𝕊⊂ℤ\\mathbb\{S\}\\subset\\mathbb\{Z\}\.

Customizable Loss Function\.To perform the constrained optimization, we propose the customizable loss function:

\(8\)ℒ\\displaystyle\\mathcal\{L\}=ℒobj\+∑1≤l≤Lℒcstrl\\displaystyle=\\mathcal\{L\}\_\{\\text\{obj\}\}\+\\sum\\limits\_\{1\\leq l\\leq L\}\\mathcal\{L\}\_\{\\text\{cstr\}\}^\{l\}The lossℒobj\\mathcal\{L\}\_\{\\text\{obj\}\}denotes the mean value of the objective attribute of the top\-ranked route in the joint system \(referred to aspoptjointp\_\{\\text\{opt\}\}^\{\\text\{joint\}\}\):

\(9\)ℒobj\\displaystyle\\mathcal\{L\}\_\{\\text\{obj\}\}=1\|𝕊\|​∑𝕊a𝒞⁡\(0\)\\displaystyle=\\dfrac\{1\}\{\|\\mathbb\{S\}\|\}\\sum\\limits\_\{\\mathbb\{S\}\}a\_\{\\mathscr\{C\}\(0\)\}The other lossℒcstrl\\mathcal\{L\}\_\{\\text\{cstr\}\}^\{l\}yields a penalty when the corresponding constraint gets violated:

\(10\)ℒcstrl\\displaystyle\\mathcal\{L\}\_\{\\text\{cstr\}\}^\{l\}=λl×max⁡\(0,ℋl−bl\)\\displaystyle=\\lambda\_\{l\}\\times\\max\(0,\\mathcal\{H\}^\{l\}\-b^\{l\}\)with

\(12\)ℋl\\displaystyle\\mathcal\{H\}^\{l\}=1\|𝕊\|​∑𝕊tiopt×a𝒞⁡\(l\)′\\displaystyle=\\dfrac\{1\}\{\|\\mathbb\{S\}\|\}\\sum\\limits\_\{\\mathbb\{S\}\}t\_\{i\_\{\\text\{opt\}\}\}\\times a\_\{\\mathscr\{C\}\(l\)\}^\{\\prime\}\(13\)bl\\displaystyle b^\{l\}=1\|𝕊\|​∑𝕊tiopt×hpoptheuristicl×\(1\+ol\)\\displaystyle=\\dfrac\{1\}\{\|\\mathbb\{S\}\|\}\\sum\\limits\_\{\\mathbb\{S\}\}t\_\{i\_\{\\text\{opt\}\}\}\\times\{h\_\{p\_\{\\text\{opt\}\}^\{\\text\{heuristic\}\}\}^\{l\}\}\\times\(1\+o\_\{l\}\)wherepoptheuristicp\_\{\\text\{opt\}\}^\{\\text\{heuristic\}\}refers to the top\-ranked route in Amap’s route\-planning system,ℋl\\mathcal\{H\}^\{l\}denotes the mean value of the constrained attribute ofpoptjointp\_\{\\text\{opt\}\}^\{\\text\{joint\}\},blb^\{l\}—the threshold—denotes the mean value of the constrained attribute ofpoptheuristicp\_\{\\text\{opt\}\}^\{\\text\{heuristic\}\}scaled by a factor of1\+ol1\+o\_\{l\}, andλl\>0\\lambda\_\{l\}\>0are hyperparameters controlling the magnitude of the constraints\. In essence,ℒcstrl\\mathcal\{L\}\_\{\\text\{cstr\}\}^\{l\}constrain the attribute value of the joint system to be less than1\+ol1\+o\_\{l\}times that of the existing system\.

Batch Sampling Method\.To enforce local constraints, we propose a novel two\-stage batch sampling method as follows\. Letp⁡\(z0\)p\(z\_\{0\}\)denote the request density atz0=\(d0,t0,w0\)∈ℤz\_\{0\}=\(d\_\{0\},t\_\{0\},w\_\{0\}\)\\in\\mathbb\{Z\}\. In each iteration, we first randomly sample a batch𝔹obj\\mathbb\{B\}\_\{\\text\{obj\}\}\. We then pick up an anchor pointzc=\(dc,tc,wc\)∈ℤz\_\{c\}=\(d\_\{c\},t\_\{c\},w\_\{c\}\)\\in\\mathbb\{Z\}based on the probabilitypp\. Next, we randomly sample a sub\-batch of requests𝔹cstr⊂𝔹obj\\mathbb\{B\}\_\{\\text\{cstr\}\}\\subset\\mathbb\{B\}\_\{\\text\{obj\}\}, within a window centered onzcz\_\{c\},\{\(d,t,w\)\|dc−Δd≤d≤dc\+Δd,tc−Δt≤t≤tc\+Δt,w=wc\}\\\{\(d,t,w\)\\,\|\\,d\_\{c\}\-\\Delta\{d\}\\leq d\\leq d\_\{c\}\+\\Delta\{d\},\\,t\_\{c\}\-\\Delta\{t\}\\leq t\\leq t\_\{c\}\+\\Delta\{t\},\\,w=w\_\{c\}\\\}, whereΔ​d=5​km\\Delta d=5\\,\\text\{km\}andΔ​c=2​hours\\Delta c=2\\,\\text\{hours\}are constants\. We calculateℒobj\\mathcal\{L\}\_\{\\text\{obj\}\}on𝔹obj\\mathbb\{B\}\_\{\\text\{obj\}\}and∑1≤l≤Lℒcstrl\\sum\\limits\_\{1\\leq l\\leq L\}\\mathcal\{L\}\_\{\\text\{cstr\}\}^\{l\}on𝔹cstr\\mathbb\{B\}\_\{\\text\{cstr\}\}\.

Hyperparameter Optimization\.Proper choice of the hyperparametersλl\\lambda\_\{l\}are critical for achieving a converged solution that satisfies all inequality constraints: a largeλl\\lambda\_\{l\}may lead to oscillation during the iteration, yet a smallλl\\lambda\_\{l\}may cause violation of the constraints\. To tackle this issue, we use scenariolizedλl,s\\lambda\_\{l,s\}, wheressdenotes a point on a grid inℤ\\mathbb\{Z\}, initialize allλl,s\\lambda\_\{l,s\}as random numbers between 0 and 1, and update them after each iteration as follows:

\(14\)λl,sn\+1=\{λl,sn\+Δλ,ℋl\>blmax​\(0,λl,sn−Δλ\),otherwise\\lambda\_\{l,s\}^\{n\+1\}=\\begin\{cases\}\\lambda\_\{l,s\}^\{n\}\+\\Delta\_\{\\lambda\}&,\\mathcal\{H\}^\{l\}\>b^\{l\}\\\\ \\text\{max\}\(0,\\lambda\_\{l,s\}^\{n\}\-\\Delta\_\{\\lambda\}\)&,\\text\{otherwise\}\\end\{cases\}wherenndenotes the index of iteration andΔλ=0\.01\\Delta\_\{\\lambda\}=0\.01is a constant\.

## 5\.EXPERIMENT

In this section, we first describe the datasets, methods, implementation details, and evaluation metrics\. Then we show the effectiveness of the customizable loss function and the joint learning framework\.

### 5\.1\.Datasets

We conduct experiments based on two datasets\. One dataset contains routing requests and GPS trajectories of anonymous users of Amap in Beijing and Shanghai from November 1, 2020 to November 7, 2020\. Each request has five fieldsq=\(t,xo,yo,xd,yd\)q=\(t,x\_\{o\},y\_\{o\},x\_\{d\},y\_\{d\}\), wherettis the timestamp when the request was received by Amap;xo,yox\_\{o\},y\_\{o\}are the longitude, latitude of the origin; andxd,ydx\_\{d\},y\_\{d\}are the longitude, latitude of the destination\. The other dataset contains information on the road networks, including the adjacency relation and attributes of the edges\. Table[1](https://arxiv.org/html/2609.19996#S5.T1)shows the statistics of the trajectories and road networks\. We randomly split the data into 80% for training and 20% for testing\.

Table 1\.Statistics of the datasets\.DatasetAttributeBeijingShanghaiUsertrajectoryNum\. of records1\.38M1\.22Mtravel time1584s1604stravel distance14\.4km14\.2kmlength of congestion472m262mNum\. of traffic lights8\.312\.7Num\. of turns9\.210\.2toll2\.15¥1\.70¥RoadnetworkNum\. of roads2\.09M2\.21MNum\. of toll roads5\.68k4\.02kNum\. of traffic lights9\.71k14\.8kNum\. of turns4\.21M4\.53M
### 5\.2\.Methods

Methods compared in the experiment are detailed as follows:

Benchmark Methods\.

- •H\-SD: Routes in H\-SD are recalled with the heuristic cost functions, and ranked according to distance\.
- •H\-ST: Routes in H\-ST are recalled with the heuristic cost functions, and ranked according to ETA\.
- •H\-Lambda: In the industry of digital map and navigation, deviation rate is widely adopted as the measure of route quality\. To lower the deviation rate, a ranking model with listwise loss function is commonly used, as elaborated below\. LetSqS\_\{q\}denote the set of routes recalled with respect to requestqq, andtqt\_\{q\}denote user trajectory\. A routep∈Sqp\\in S\_\{q\}is labelled as 1 if it completely coincides withtqt\_\{q\}; 0 otherwise\. Sorted according to such a label,SqS\_\{q\}becomes an ordered list, which serves as the ground truth of a ranking model\. In H\-Lambda, we train a LambdaMART model\([Kosiur, 2001](https://arxiv.org/html/2609.19996#bib.bib1)\)to rank the heuristic routes\. We set the number of trees at 1150, feature sample rate at 0\.5, and data sample rate at 0\.5\.

Customizable and Jointly Optimized Route Planning\.

- •H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}: H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}denotes a route\-planning system comprising the heuristic routes, and a ranking model \(MLP\) trained with the customized loss function\. We use two layers for the MLP, and ELU as the activation\. The hidden unit of each layer is 64\.
- •H\-CJRPR′\\text\{CJRP\}\_\{\\text\{R\}\}^\{\\prime\}: H\-CJRPR′\\text\{CJRP\}\_\{\\text\{R\}\}^\{\\prime\}is the same as H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}, except for using the plain single\-stage random batch sampling with fixedλ\\lambda\.
- •E\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}: In CRP, properties of the alternative routes depend on three control parameters\(α,β,γ\)\(\\alpha,\\beta,\\gamma\), whereα\\alphadenotes the maximum allowed stretch,β\\betadenotes the maximum allowed route sharing, andγ\\gammadenotes the threshold guaranteeing local optimality\. We relax the control parameters to recall additional alternative routes and denote such an enlarged route set bySES\_\{E\}\. E\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}denotes a route\-planning system comprising the enlarged set of routes, and a ranking model \(MLP\) trained with the customized loss function, where MLP has the same structure as in H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\.
- •M\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}: M\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}denotes a route\-planning system comprising the union of the heuristic route set and the Pareto set, and a ranking model \(MLP\) trained with the customized loss function, where MLP has the same structure as in H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\.
- •CJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}:CJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}denotes a route\-planning system comprising the union of the heuristic routes and the routes recalled with the learned cost functions, and a ranking model trained with the customized loss function, where MLP has the same structure as in H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\.

Among the CJRP family,CJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}, which learns a set of cost functions to compensate the inefficiency of the existing heuristic cost functions, achieves the best balance between route quality and query response time\.

### 5\.3\.Implementation Details

In Table[2](https://arxiv.org/html/2609.19996#S5.T2), we show the representative features of the ranking model, which are shared across all methods\. In CRP, we set the control parameters asα=0\.85\\alpha=0\.85,ϵ=0\.3\\epsilon=0\.3, andγ=0\.2\\gamma=0\.2for the heuristic route set, andα=0\.9\\alpha=0\.9,ϵ=0\.3\\epsilon=0\.3, andγ=0\.1\\gamma=0\.1for the enlarged route set\. In CJRP models, allλ\\lambdas controlling the magnitude of the constraints are initialized as random numbers between 0 and 1\. To train the CJRP models, we use Adam optimizer with initial learning rate 0\.001 and decay rate 0\.98\. The ETA model is implemented with scikit\-learn; the deviation rate model and H\-Lambda are implemented with LightGBM; the neural network models are implemented with TensorFlow\. The training and inference of all models are conducted on seven servers each with 512GB RAM and 96 cores\.

Table 2\.Representative features in the ranking model\.Feature TypeFeaturesTemporalhour, day of week, holiday, etc\.Spatialcity, POI category, etc\.Static attributedistance, length of freeways, free\-flow travel time, number of traffic lights, number of driving maneuvers, toll, etc\.Dynamic attributelive travel time, ETA, length of traffic congestion at the request time, deviation rate, etc\.Badcase attributelocal detour, length of the alleyways, frequent switching between main road and auxiliary road, etc\.
### 5\.4\.Evaluation Metrics

We use the following four route preferences222Without loss of generality, we simplify the constraints from those in\-service\.to evaluate model performance:

- •Regular: It recommends a route with the lowest deviation rate and tolerable degradation of other attributes\. The objective attribute is deviation rate\. The constrained attributes \(threshold offsetsolo\_\{l\}\) are ETA \(0\.5%\), distance \(0\.5%\), and length of congested roads \(0%\)\.
- •Fastest: It recommends a route with the shortest travel time and tolerable degradation of other attributes\. The objective attribute is ETA\. The constrained attributes \(threshold offsetsolo\_\{l\}\) are distance \(5%\), number of traffic lights \(0%\), and length of alleyways \(0%\)\.
- •Avoid tolls: It recommends a route with less toll roads than the regular route\. The objective attribute is toll\. The constrained attributes \(threshold offsetsolo\_\{l\}\) are ETA \(5%\) and distance \(5%\)\.
- •Economic: This option is provided for ride\-hailing users\. It recommends a route with the lowest order price and tolerable degradation of other attributes\. The real pricing formula of an order is fairly complicated; we use a simplified version instead in this paper:price \(¥\)=3\.15×distance \(kilometer\)\+0\.7×ETA \(minute\)\+toll \(¥\)\\text\{price \(\\textyen\)\}=3\.15\\times\\text\{distance \(kilometer\)\}\+0\.7\\times\\text\{ETA \(minute\)\}\+\\text\{toll \(\\textyen\)\}\. The objective attribute is order price\. The constrained attributes \(threshold offsetsolo\_\{l\}\) are ETA \(10%\) and distance \(10%\)\.

The above implementation of these preferences are determined based on study of user feedback\. We use the corresponding objective attribute and average response time \(ART\) as the evaluation metrics for each preference\.

### 5\.5\.Performance Comparison

Effectiveness in Customizing Route Attributes\.We conduct experiments on the regular preference to validate the effectiveness of H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}in customizing route attributes\.

We train H\-Lambda and H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}, with the regular loss function as detailed in Section[5\.4](https://arxiv.org/html/2609.19996#S5.SS4)\. The training loss curve of H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}is shown in Figure[3](https://arxiv.org/html/2609.19996#S5.F3)\. Table[3](https://arxiv.org/html/2609.19996#S5.T3)shows the mean values of the objective variables and constrained variables, where the deviation rate and ETA are predicted using estimators described in Section[3](https://arxiv.org/html/2609.19996#S3)\. In line with the customized loss function, H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}keeps ETA, distance, and length of congested roads within the imposed constraints, and achieves a significant improvement in deviation rate over H\-Lambda\. Also, all constraints are ensured locally valid across the parametric space of requests, as illustrated in Figure[4](https://arxiv.org/html/2609.19996#S5.F4)\.

We further deploy the two models in Amap’s online routing service in Beijing and Shanghai, from December 19 to December 21\. As A/B testing, we randomly allocate the real\-time routing requests to the two models\. As shown in Table[4](https://arxiv.org/html/2609.19996#S5.T4), H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}satisfies the constraint on travel time, and achieves a decent improvement in deviation rate over H\-Lambda\. Notice that the improvement in online evaluation is smaller compared to its offline counterpart\. This is attributed to the inadequate predicative capability of the deviation rate estimator, which can be considerably strengthened by including stronger discriminative features, such as the individualized characteristics\. To showcase the effect of H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}, we provide an example in Figure[5](https://arxiv.org/html/2609.19996#S5.F5)\. Compared to the recommended route in H\-Lambda, the top\-ranked route in H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}has fewer driving maneuvers and traffic lights, looks smoother, and is much easier to follow\. Intuitively, this route sacrifices a few minutes and kilometers in exchange for a lower deviation rate\.

![Refer to caption](https://arxiv.org/html/2609.19996v1/loss_step_all.png)Figure 3\.Training loss curve of H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\.![Refer to caption](https://arxiv.org/html/2609.19996v1/scene_constrains_left_right.png)Figure 4\.Comparison ofCJRP′\\text\{CJRP\}^\{\\prime\}\(left\) andCJRP\(right\) on local constraint on the length of congested roads\. Each point in the graph represents a distinct routing scenario\. Clearly, much fewer scenarios violate the constraint inCJRPthan inCJRP′\\text\{CJRP\}^\{\\prime\}\.Table 3\.Comparisons between H\-Lambda and H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}on the regular preference, based on offline evaluation\.DatasetBeijingShanghaiModelH\-LambdaH\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}H\-LambdaH\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}deviation rate33\.9%32\.2%35\.5%33\.9%ETA1830 s1811 s1802 s1789 sdistance18148 m18176 m17136 m17122 mcongestion412 m393 m197 m190 mTable 4\.Comparisons between H\-Lambda and H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}on the regular preference in an online A/B testing\.DatasetBeijingShanghaiModelH\-LambdaH\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}H\-LambdaH\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}deviation rate36\.1%35\.3%38\.9%38\.2%travel time1913 s1924 s2031 s2021 sFigure 5\.Case study: H\-Lambda \(left\) versus H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\(right\) on the regular preference\.![Refer to caption](https://arxiv.org/html/2609.19996v1/libra_case_gray_left.png)
![Refer to caption](https://arxiv.org/html/2609.19996v1/libra_case_gray_right.png)

Figure 6\.Case study: H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\(left\) versusCJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}\(right\) on the economic preference\.![Refer to caption](https://arxiv.org/html/2609.19996v1/libra_case_economic_left.png)
![Refer to caption](https://arxiv.org/html/2609.19996v1/libra_case_economic_right.png)

Customizability\.We compare the offline performance of the CJRP family and the benchmarks on three other common preferences, as listed in Section[5\.4](https://arxiv.org/html/2609.19996#S5.SS4)\. Table[5](https://arxiv.org/html/2609.19996#S5.T5)show the results\. For every preference, all CJRP models significantly outperform the benchmarks, verifying the customizability of the proposed framework\.

Table 5\.Comparisons on various route preferences in Beijing and Shanghai, based on the offline evaluation\. The attribute values of H\-Lambda are the original numbers\. To better contrast the performance, the attribute values of other models are displayed as the difference between the original numbers and those of H\-Lambda\. Numbers in the brackets are the corresponding percentage differences\. We setM=5M=5\(number of learnable cost functions\) inCJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}\.\[t\]FastestAvoid tollsEconomicModelobjcstr\-1cstr\-2cstr\-3objcstr\-1cstr\-2objcstr\-1cstr\-2ETAdistancetraffic lightalleywaytollETAdistancepriceETAdistanceH\-Lambda1280s10824m9\.79\.0m0\.83¥1280s10824m49\.86¥1280s10824mH\-ST\-39s353m \(3%\)\-0\.3 \(\-3%\)1\.4m \(16%\)0\.26¥\-39s \(\-3%\)353m \(3%\)0\.93¥\-39s \(\-3%\)353m \(3%\)H\-SD118s\-606m \(\-6%\)2\.9 \(30%\)1\.6m \(18%\)\-0\.23¥118s \(9%\)\-606m \(\-6%\)0\.76¥118s \(9%\)\-606m \(\-6%\)H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\-37\.9s361m \(3%\)\-0\.3 \(\-3%\)\-0\.1m \(\-1%\)\-0\.48¥46s \(4%\)207m \(2%\)\-1\.42¥32s \(3%\)\-485m \(\-4%\)E\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\-41\.5s414m \(4%\)\-0\.2 \(\-2%\)\-0\.2m \(\-2%\)\-0\.50¥46s \(4%\)288m \(3%\)\-1\.56¥35s \(3%\)\-528m \(\-5%\)CJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}\-64\.5s359m \(3%\)\-1\.0 \(\-10%\)\-0\.3m \(\-3%\)\-0\.64¥56s \(4%\)290m \(3%\)\-1\.87¥37s \(3%\)\-615m \(\-6%\)M\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\-69\.1s325m \(3%\)\-1\.1 \(\-11%\)\-0\.1m \(\-1%\)\-0\.65¥59s \(5%\)124m \(1%\)\-2\.02¥30s \(2%\)\-634m \(\-6%\)

Table 6\.The weights of the cost functions\. H1 and H2 denote the two heuristic cost functions: “fastest in the free flow period” and “avoid congestion\.” L1 to L5 denote the learned cost functions ofCJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}for the economic preference\. Every cost function is a linear combination of the five attributes, and the values are the corresponding weights\.AttributeH1H2L1L2L3L4L5free\-flow travel time \(s\)140565000distance \(m\)1111111live travel time \(s\)01430120traffic light1141145170000maneuver466462504397000Table 7\.Comparison of the average response timeModelNum\. of routesARTrecall\\text\{ART\}\_\{\\text\{recall\}\}ARTranking\\text\{ART\}\_\{\\text\{ranking\}\}H\-Lambda7196 ms98 msH\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}7196 ms97 msE\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}28228 ms319 msCJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}12222 ms160 msM\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}4815793 ms603 msEffectiveness of the Learned Cost Functions\.We further compare the performance among the CJRP models, which differ only in the recall stage\. First,CJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}considerably outperforms H\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}\. 26\.3% of the top\-ranked routes inCJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}are solely recallable with the learned cost functions, suggesting the inefficiency of the existing heuristic cost functions\. We show an example from the economic preference in Figure[6](https://arxiv.org/html/2609.19996#S5.F6)\. The top\-ranked route inCJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}, which is recalled with a learned cost function—L2 as shown in Table[6](https://arxiv.org/html/2609.19996#S5.T6), has a minor increase in ETA, but a 15% lower price\. Such an improvement is attributed to the optimality of the learned cost function towards the preference: the weight ratio of travel time to distance in L2 is 5, about the same as that—3\.7— in the pricing formula\. Secondly,CJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}, though with fewer routes recalled, substantially outperforms E\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}, validating the effectiveness of the optimality of the learned cost functions\. Furthermore, as mentioned above, multi\-objective Dijkstra has exponential time complexity, which limits its application in real\-time services\. Figure[7](https://arxiv.org/html/2609.19996#S5.F7)illustrates this point on our dataset\. Compared to M\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\},CJRPJ\\text\{CJRP\}\_\{\\text\{J\}\}achieves a similar level of performance with a much smaller and practical response time as shown in Table[7](https://arxiv.org/html/2609.19996#S5.T7), demonstrating the superiority of the proposed framework in large\-scale real\-world application\.

![Refer to caption](https://arxiv.org/html/2609.19996v1/mor_recall_cost_log.png)Figure 7\.Exponential time complexity of MOD\.![Refer to caption](https://arxiv.org/html/2609.19996v1/benefits_of_w.png)Figure 8\.Effect of the number of learnable cost functions on the economic preference\. Y\-axis denotes the difference of order price between H\-Lambda and the CJRP family\.Effect of the Number of Learnable Cost Functions\.For a preprocessing\-based route\-planning scheme like CRP, each additional cost function consumes extra computing resources \(CPU and memory\)\. To explore the balance between performance and resource cost, we study the effect of the number of learnable cost functions on the economic preference\. Figure[8](https://arxiv.org/html/2609.19996#S5.F8)shows the results\. If we consider the improvement of M\-CJRPR\\text\{CJRP\}\_\{\\text\{R\}\}as the maximum improvement obtainable, then 3 \(5\) extra cost functions suffice to achieve 80% \(90%\) of the maximum\.

## 6\.CONCLUSION

In this paper, we propose a novel deep architecture for jointly optimizing the cost functions and ranking model in a route\-planning system\. We run a multi\-objective Dijkstra algorithm offline to compute the Pareto\-optimal set for each routing request and deem it as the complete candidate set\. Exploiting the property of such a set, we design a neural network structure that performs a shortest\-path search\. This structure, together with a cascaded MLP\-based ranking module, emulates the process of route planning in a fully differentiable manner\. To further adapt the joint model to the various route preferences, we propose a customizable loss function, constructed with unbiased estimators for route attributes\. In addition, we propose a novel batch sampling method that ensures local validity of the constraints\. Finally, evaluations on real\-world datasets show that our architecture significantly outperforms state\-of\-the\-art methods in both route quality and customizability\.

## References

- Abrahamet al\.\(2010\)I\. Abraham, D\. Delling, A\. V\. Goldberg, and R\. F\. WerneckAlternative routes in road networks\.InInternational Symposium on Experimental Algorithms,pp\. 23–34\.Cited by:[§4\.2](https://arxiv.org/html/2609.19996#S4.SS2.p1.1)\.
- Bastet al\.\(2016\)H\. Bast, D\. Delling, A\. Goldberg, M\. Müller\-Hannemann, T\. Pajor, P\. Sanders, D\. Wagner, and R\. F\. WerneckRoute planning in transportation networks\.InAlgorithm engineering,pp\. 19–80\.Cited by:[§1](https://arxiv.org/html/2609.19996#S1.p2.1),[§2](https://arxiv.org/html/2609.19996#S2.p2.1)\.
- Dellinget al\.\(2017\)D\. Delling, A\. V\. Goldberg, T\. Pajor, and R\. F\. WerneckCustomizable route planning in road networks\.Transportation Science51\(2\),pp\. 566–591\.Cited by:[§2](https://arxiv.org/html/2609.19996#S2.p2.1),[§4\.2](https://arxiv.org/html/2609.19996#S4.SS2.p1.1)\.
- Dellinget al\.\(2015\)D\. Delling, T\. Pajor, and R\. F\. WerneckRound\-based public transit routing\.Transportation Science49\(3\),pp\. 591–604\.Cited by:[§2](https://arxiv.org/html/2609.19996#S2.p2.1),[§4\.3](https://arxiv.org/html/2609.19996#S4.SS3.p1.1)\.
- Geisbergeret al\.\(2012\)R\. Geisberger, P\. Sanders, D\. Schultes, and C\. VetterExact routing in large road networks using contraction hierarchies\.Transportation Science46\(3\),pp\. 388–404\.Cited by:[§2](https://arxiv.org/html/2609.19996#S2.p2.1)\.
- Goldberg and Harrelson \(2005\)A\. V\. Goldberg and C\. HarrelsonComputing the shortest path: a search meets graph theory\.\.InSODA,Vol\.5,pp\. 156–165\.Cited by:[§2](https://arxiv.org/html/2609.19996#S2.p2.1)\.
- Hartet al\.\(1968\)P\. E\. Hart, N\. J\. Nilsson, and B\. RaphaelA formal basis for the heuristic determination of minimum cost paths\.IEEE transactions on Systems Science and Cybernetics4\(2\),pp\. 100–107\.Cited by:[§2](https://arxiv.org/html/2609.19996#S2.p2.1)\.
- Kosiur \(2001\)D\. KosiurUnderstanding policy\-based networking\.2nd\. edition,, Vol\.,Wiley,New York, NY\.Note:Cited by:[3rd item](https://arxiv.org/html/2609.19996#S5.I1.i3.p1.1)\.
- Luoet al\.\(2013\)W\. Luo, H\. Tan, L\. Chen, and L\. M\. NiFinding time period\-based most frequent path in big trajectory data\.InProceedings of the 2013 ACM SIGMOD international conference on management of data,pp\. 713–724\.Cited by:[§2](https://arxiv.org/html/2609.19996#S2.p3.1)\.
- Marler and Arora \(2004\)R\. T\. Marler and J\. S\. AroraSurvey of multi\-objective optimization methods for engineering\.Structural and multidisciplinary optimization26\(6\),pp\. 369–395\.Cited by:[§1](https://arxiv.org/html/2609.19996#S1.p2.1)\.
- Martins \(1984\)E\. Q\. V\. MartinsOn a multicriteria shortest path problem\.European Journal of Operational Research16\(2\),pp\. 236–245\.Cited by:[§1](https://arxiv.org/html/2609.19996#S1.p2.1),[§2](https://arxiv.org/html/2609.19996#S2.p2.1)\.
- Schaferet al\.\(2001\)J\. B\. Schafer, J\. A\. Konstan, and J\. RiedlE\-commerce recommendation applications\.Data mining and knowledge discovery5\(1\),pp\. 115–153\.Cited by:[§2](https://arxiv.org/html/2609.19996#S2.p4.1)\.
- Sinhaet al\.\(2017\)A\. Sinha, D\. F\. Gleich, and K\. RamaniDeconvolving feedback loops in recommender systems\.arXiv preprint arXiv:1703\.01049\.Cited by:[§1](https://arxiv.org/html/2609.19996#S1.p2.1)\.
- Vinyalset al\.\(2015\)O\. Vinyals, M\. Fortunato, and N\. JaitlyPointer networks\.Advances in neural information processing systems28,pp\. 2692–2700\.Cited by:[§2](https://arxiv.org/html/2609.19996#S2.p5.1)\.
- Wanget al\.\(2019\)J\. Wang, N\. Wu, W\. X\. Zhao, F\. Peng, and X\. LinEmpowering a\* search algorithms with neural networks for personalized route recommendation\.InProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,pp\. 539–547\.Cited by:[§1](https://arxiv.org/html/2609.19996#S1.p2.1),[§2](https://arxiv.org/html/2609.19996#S2.p3.1)\.
- Zhaoet al\.\(2019\)Z\. Zhao, L\. Hong, L\. Wei, J\. Chen, A\. Nath, S\. Andrews, A\. Kumthekar, M\. Sathiamoorthy, X\. Yi, and E\. ChiRecommending what video to watch next: a multitask ranking system\.InProceedings of the 13th ACM Conference on Recommender Systems,pp\. 43–51\.Cited by:[§2](https://arxiv.org/html/2609.19996#S2.p4.1)\.