# Impact of URI Canonicalization on Memento Count

Mat Kelly  0000-0002-0236-7389<EMAIL_ADDRESS>Old Dominion
UniversityDepartment of Computer ScienceNorfolkVirginiaUSA ,  Lulwah M. Alkwai
<EMAIL_ADDRESS>Old Dominion UniversityDepartment of Computer
ScienceNorfolkVirginiaUSA ,  Michael L. Nelson  0000-0003-3749-8116
<EMAIL_ADDRESS>Old Dominion UniversityDepartment of Computer
ScienceNorfolkVirginiaUSA ,  Michele C. Weigle  0000-0002-2787-7166
<EMAIL_ADDRESS>Old Dominion UniversityDepartment of Computer
ScienceNorfolkVirginiaUSA and  Herbert Van de Sompel  Los Alamos National
LaboratoryLos AlamosNew MexicoUSA<EMAIL_ADDRESS>
###### Abstract.

Quantifying the captures of a URI over time is useful for researchers to
identify the extent to which a Web page has been archived. Memento TimeMaps
provide a format to list mementos (URI-Ms) for captures along with brief
metadata, like Memento-Datetime, for each URI-M. However, when some URI-Ms are
dereferenced, they simply provide a redirect to a different URI-M (instead of
a unique representation at the datetime), often also present in the TimeMap.
This infers that confidently obtaining an accurate count quantifying the
number of non-forwarding captures for a URI-R is not possible using a TimeMap
alone and that the magnitude of a TimeMap is not equivalent to the number of
representations it identifies. In this work we discuss this particular
phenomena in depth. We also perform a breakdown of the dynamics of counting
mementos for a particular URI-R (google.com) and quantify the prevalence of
the various canonicalization patterns that exacerbate attempts at counting
using only a TimeMap. For google.com we found that 84.9% of the URI-Ms result
in an HTTP redirect when dereferenced. We expand on and apply this metric to
TimeMaps for seven other URI-Rs of large Web sites and thirteen academic
institutions. Using a ratio metric $DI$ for the number of URI-Ms without
redirects to those requiring a redirect when dereferenced, five of the eight
large web sites’ and two of the thirteen academic institutions’ TimeMaps had a
ratio of ratio less than one, indicating that more than half of the URI-Ms in
these TimeMaps result in redirects when dereferenced.

††article: -1††copyright: none

##  1\. Introduction

Memento TimeMaps serve as an index for the mementos for an original resource
(URI-R) contained in an archive (Van de Sompel et al., 2013). Web archives
return TimeMaps with a list of identifiers (URI-Ms) for the HTTP transactions
observed at archival time. TimeMaps have generally been used as a count of the
number of representations of a URI-R present in an archive. But, TimeMaps may
include URI-Ms for archived representations (HTTP 2XX), archived redirections
(HTTP 3XX), and archived errors (HTTP 4XX or 5XX) (Fielding and Reschke,
2014b). Only the URI-Ms that result in an HTTP 2XX when dereferenced match the
general notion of a “capture” of the contents of a webpage. But, the status
that results when a URI-M is dereferenced (to the extent of returning an
archived entity body) is not present in a TimeMap. Further, TimeMaps do not
explicitly return a “count” value to indicate the number of mementos listed in
the TimeMap that produce a non-redirecting (non-3XX) HTTP status code when
dereferenced. This can cause problems when using the number of URI-Ms in a
TimeMap as a proxy for the number of captures of a Web page.

Various tools (Alam and Nelson, 2016; Jordan et al., 2015; Kelly et al., 2014)
and access points into the Web archives return a different count of the number
of captures for a URI-R depending on the heuristic implemented and the source
of the archival listings. For example, the Internet Archive’s web interface
when queried with the URI-R example.com states, “Saved 11,771 times between
January 20, 2002 and May 20, 2016”. The file returned from Internet Archive’s
CDX endpoint returns 69,162 entries. The TimeMap from Internet Archive for
example.com contains 40,641 URI-Ms with a rel value of “memento”. The
heuristic of determining how many captures are represented by URI-Ms in a
TimeMap cannot be completed without dereferencing.

Researchers can use the inline metadata about the URI-M, without the need to
dereference the URI-M in a TimeMap, including its temporal ordering, datetime
(through the datetime HTTP Link attribute (Van de Sompel et al., 2013)), etc.
to infer characteristics about a dereferenced memento. However, dereferencing
some URI-Ms in a TimeMap produces an HTTP redirect (Fielding and Reschke,
2014b) that instructs the client to access a URI-M with a different datetime,
to obtain the requested content. For example, a TimeMap for http://vimeo.com
from Internet Archive contained 199,262 URI-Ms with an associated “rel” value
of “memento”. However, when a user accesses over 57% of these URI-Ms, an HTTP
Redirect is returned pointing to another memento whose URI-M is in the TimeMap
that returns a HTTP Status OK. A different extreme of memento count results
when a user accesses the TimeMap from http://odu.edu, whose percentage of
redirects is around 9.7% of the URI-Ms listed.

Redirection in a Web archive can be attributed to a variety of
canonicalization rules including a scheme change (e.g., http to https), an
obsolete subdomain (e.g., www2 to www), a slash added to a URI
(http://foo.com/~joe to http://foo.com/~joe/), among others. Preserving and
replaying these redirects allows an archive to accurately reproduce the HTTP
transactions that would have occurred when the URI being accessed resided on
the live Web.

When a URI-M in a TimeMap is dereferenced, it may redirect to another URI-M
listed in the TimeMap. Because of this, the heuristic of counting URI-Ms with
relation values of “memento” is an inaccurate means of determining the number
of unique representations inferred from a TimeMap. We further emphasize the
distinction per the Memento specification that the identifiers for mementos
(URI-Ms) in a TimeMap are identifiers for archived HTTP transactions (e.g.,
transmission of HTTP 2XX, 3XX, 4XX, etc.) rather than identifiers for
representations.

Based on the number of URI-Ms in a TimeMap not necessarily resolving to unique
mementos when archival redirects are followed, we examined the mementos from
contemporarily large TimeMaps to evaluate the patterns and schemes used in
Memento canonicalization. Through this, we identify the difference between the
number of mementos available as reported by the TimeMap through naive “rel”
counting heuristics to the temporally unique mementos identified once these
mementos are dereferenced.

##  2\. Background

This section includes background information and an overview of the state-of-
the-art of archival technologies relevant to this work including Memento
aggregation, URI canonicalization, archival indexing formats, and URI-R
opacity.

###  2.1. Memento Aggregation

⬇

<http://example.com>; rel="original",

<http://web.archive.org/web/20020120142510/http://example.com/>; rel="first
memento"; datetime="Sun, 20 Jan 2002 14:25:10 GMT",

<http://web.archive.org/web/20020804094019/http://www.example.com/>;
rel="memento"; datetime="Sun, 04 Aug 2002 09:40:19 GMT",

<http://web.archive.org/web/20160728014649/http://www.example.com/>;
rel="memento"; datetime="Thu, 28 Jul 2016 01:46:49 GMT",

<http://web.archive.org/web/20160728114745/http://www.example.com>;
rel="memento"; datetime="Thu, 28 Jul 2016 11:47:45 GMT",

<http://web.archive.org/web/20160728123024/http://example.com/>; rel="last
memento"; datetime="Thu, 28 Jul 2016 12:30:24 GMT",

<http://localhost:1208/timemap/link/http://example.com>;
anchor="http://example.com"; rel="timemap"; type="application/link-format",

<http://localhost:1208/timegate/http://example.com>;
anchor="http://example.com"; rel="timegate"

Figure 1. A partial Link formatted TimeMap from a local instance of MemGator.
Highlighted rel values constitute inclusion in the sum described in Equations
1 and 2.

The Memento Framework (Van de Sompel et al., 2013) allows navigation of Web
archives in the dimension of time using content from Web archives and resource
versioning systems. A Memento TimeMap (Figure 1) is a structured list of
identifiers (URI-Ms) for archived captures (mementos) returned from an archive
when queried with a URI-R as the parameter. A TimeMap may also contain
references to other TimeMaps and TimeGates.

A Memento aggregator is a software implementation of Memento that takes a URI
as the parameter, queries multiple supported archives, combines and temporally
orders the returned mementos, and returns this list as a TimeMap to the user.
We used the MemGator (Alam and Nelson, 2016) implementation of a Memento
aggregator in collecting data for our analysis. MemGator provides its own
heuristic for determining and reporting the number of mementos present in an
aggregated TimeMap using the non-standard X-Memento-Count HTTP header. Despite
this, we used the contents of the aggregated TimeMap returned from MemGator
instead of this header as the basis for further investigating the number of
mementos present.

###  2.2. URI Canonicalization

URI canonicalization associates differently formatted URIs (Ohye and Kupke,
2012). For example, http://example.com might be associated with:

  * •

http://www.example.com

  * •

https://www.example.com

  * •

http://example.com/

  * •

http://example.com/index.html

  * •

http://example.com/#articles

Canonicalization allows after-the-fact clustering of URIs that likely
reference the same resource. As URI schemes from a Web site change over time,
canonicalization is critical for retaining a cohesive, comprehensive listing
of the mementos available for a Web page. Internet Archive’s Wayback CDX
Server API111https://github.com/internetarchive/wayback/tree/master/wayback-
cdx-server and endpoint222Example access at
http://web.archive.org/cdx/search/cdx?url=example.com is one of multiple
endpointshttps://archive.org/help/wayback_api.phphttps://archive.org/help/wayback_api.php
that provides access to the indexes of the archive’s holdings. A partial
example (that corresponds with the TimeMap shown in Figure 1) of the data
returned from Internet Archive’s CDX server is shown in Figure 2. As an
alternative to their Memento endpoint (Nelson, 2013), the CDX endpoint
provides the HTTP status code of the capture as well as Sort-friendly URL
Reordering Transformed (SURT) URIs. Part of the SURT-generation process
involves canonicalizing the URI-R. A canonicalized URI is present in the first
space-delimited field (Figure 2) where the “www” subdomain is not present
despite being part of the URI in the query parameter. The non-canonicalized
URI-R attributed to the record in the CDX is available as the third field in
the CDX record. Figure 2 shows the URI-R variations including no subdomain,
the “www” subdomain, with and without a trailing slash, and the explicit
inclusion of the port number as all canonicalizing to the same URI in the CDX.

⬇

com,example)/ 20020120142510 http://example.com:80/ text/html 200
HT2DYGA5UKZCPBSFVCV3JOBXGW2G5UUA 1792

com,example)/ 20020804094019 http://www.example.com:80/ text/html 200
UY3I2DT2AMWAY6DECFCFYMT5ZOTFHUCH 457

com,example)/ 20160728014649 http://www.example.com/ unk 302
3I42H3S6NNFQ2MSVX7XZKYAYSCX5QBYJ 339

com,example)/ 20160728114745 http://www.example.com unk 302
3I42H3S6NNFQ2MSVX7XZKYAYSCX5QBYJ 340

com,example)/ 20160728123024 http://example.com/ text/html 200
ASIFPQKKLDWATFDIO1OJJ3NSK34KLLMN 577

Figure 2. A CDX response returned from Internet Archive’s CDX Server. The
space-delimited fields are representative of the canonicalized (SURTed) URI,
datetime, original URI, MIME type of original document (where applicable),
HTTP response code, digest of WARC response record, and length of response
record.

###  2.3. Archival Indexing

A CDX record with a 3XX HTTP status code does not contain the ultimate URI-M
that the user will experience when the URI-M is dereferenced. Further, the CDX
in Figure 2 is only representative of IA’s holdings. The corresponding service
of aggregating CDX records in an entity like Memento’s concept of combining of
TimeMaps from different archives through a Memento aggregator does not exist
in standard practice for CDX files. Archives that provide a Memento endpoint
are not required and frequently do not expose a CDX endpoint like Internet
Archive. This prevents simply referencing all aggregated archives’ CDX files
for a URI to determine the non-redirecting count of mementos. In this work, we
utilize the aggregated holdings of multiple Web archives as well as the CDXJ
format (Alam et al., 2015), an extension of CDX. MemGator’s CDXJ generation is
derived from the archives’ Memento endpoints, specifically their Link
formatted TimeMaps, and transformed into the CDXJ format that allows quicker,
more reliable parsing of the datetime that the included URI-Ms represent.

###  2.4. Opacity of URI-Ms

It is tempting to extract URI-R and Memento-Dateime values directly from URI-
Ms. For example, it is likely that
http://web.archive.org/web/20140417054441/http://google.com/ is a memento for
http://google.com appeared at April 17, 2014 at 05:44:41 GMT. However, we
cannot be sure until we dereference the URI-M and check its response headers
for the values in rel="original" and Memento-Datetime. While it is unlikely
that the IA will deceive us, the URI-M may redirect to another URI-M with a
different Memento-Datetime, or in the case of an archived HTTP redirection,
the URI-M might end up at an altogether different URI-R (AlSum et al., 2013).
Furthermore, some archives issue URI-Ms without semantics — for example these
URI-Ms are all mementos for google.com but neither this nor the Memento-
Datetime can be ascertained without dereferencing:
webcitation.org/query?id=1398456230796350, archive.is/sz8b9, and
perma.cc/H3YY-BQN5. For these reasons, we treat URI-Ms as fully opaque (Jacobs
and Walsh, 2004) and dereference all URI-Ms to extract values for URI-R and
Memento-Datetime.

##  3\. Related Work

Bar-Yossef et al. (Bar-Yossef et al., 2004) introduced the term, “Soft 404s”
to identify Web pages that report a status code other than HTTP 404 despite
the page not existing. Meneses et al. (Meneses et al., 2012) described the
process of identifying “Soft 404s” based on a signature of the page’s
contents. In this work we describe “soft 3XXs” where content is returned from
an archive with a status code of 200 yet the contents of the capture consist
of an archived HTTP 3XX redirect. With archives that implement Memento, the
Accept-Datetime header instructs the archive to return the originally archived
status code (Section 6.1).

AlSum et al. (AlSum et al., 2013) analyzed memento redirection patterns
relating to HTTP redirects to supply the user with the correct memento when a
redirect is encountered in the archives. They introduced the notion of “URI
stability” to give a quantitative measure of the presence of HTTP 3XX status
codes that result when URI-Ms in TimeMaps are dereferenced.

Rosenthal has discussed Memento aggregator merits and downsides. He cautioned
against using TimeMap magnitude for determining the number of URI-Ms
available, stating, “Even if we assume that an archive is correct in
announcing that it contains a valid copy of the resource at a particular URL
at a particular time, that does not imply that it is willing to satisfy a
browser’s request for that copy.” (Rosenthal, 2013).

Archive | Memento count
---|---
Internet Archive | 636,246
Archive-It | 62,828
Webcitation | 7,551
Stanford Web Archive | 4,734
UK National Archives Web Archive | 1,510
Archive.is | 1,301
PRONI Web Archive | 173
UK Parliament Web Archive | 127
Total | 714,470
Table 1. Distribution of mementos for google.com for a collection of archives
defined by a locally deployed Memento aggregator.

##  4\. Data Collection

To analyze the degree to which archival identifiers result in redirects, we
needed to acquire the HTTP response headers for all URI-Ms accumulated from
multiple Web archives for a URI-R. The concept of a Memento aggregator allows
us to accomplish this task, albeit parsing the standardized Link formatted
resulting TimeMaps is potentially prone to error.

We deployed a local instance of MemGator333http://github.com/oduwsdl/memgator
version 1.0-RC4 configured to query the archives listed in Table 1. The
MemGator instance was initialized with 25 minutes as the value for the
“restimeout” (response timeout for each archive) and “hdrtimeout” (header
timeout for each archive) parameters. Declaring these timeout values ensured
that the server portion of data collection was not prematurely returned
because of network latency with communication to the considered archives. Our
client script that queried the local MemGator instance was also setup to
access this instance with equally large timeout values.

We leveraged MemGator’s CDXJ (Alam et al., 2015) interface (example output in
Figure 3) for simple datetime extraction, structured JSON-formatted metadata
of each memento’s attributes, and more human readable output compared to the
conventional Link (Figure 1) or JSON formatted TimeMaps. Collection was run on
a late 2013 MacBook Pro running OS X version 10.11.4 with a 2.4 GHz Intel i5
processor, 8 GB of RAM, and a 250 GB SSD disk. Data was collected mid-May,
2016. We performed an initial analysis of the mementos contained within the
TimeMap without dereferencing any mementos. The client script to query the
local MemGator was created in Python 2.7.10 using the “requests”
library444http://python-requests.org and the built-in JSON parser.

⬇

@meta {"original_uri": "http://example.com"}

@meta {"timegate_uri": "http://localhost:1208/timegate/http://example.com"}

@meta {"timemap_uri": {

"link_format": "http://localhost:1208/timemap/link/http://example.com",

"json_format": "http://localhost:1208/timemap/json/http://example.com",

"cdxj_format": "http://localhost:1208/timemap/cdxj/http://example.com"

}

…

20090418233448 {"uri":
"http://web.archive.org/web/20090418233448/http://www.example.com/", "rel":
"memento", "datetime": "Sat, 18 Apr 2009 23:34:48 GMT"}

20090421223547 {"uri":
"http://wayback.vefsafn.is/wayback/20090421223547/http://www.example.com/",
"rel": "memento", "datetime": "Tue, 21 Apr 2009 22:35:47 GMT"}

20090421231335 {"uri":
"http://webarchive.loc.gov/all/20090421231335/http://www.example.com/", "rel":
"memento", "datetime": "Tue, 21 Apr 2009 23:13:35 GMT"}

…

Figure 3. A partial CDXJ formatted TimeMap returned from a local instance of
MemGator containing URI-Ms from multiple archives.

##  5\. Analysis based on TimeMaps

We obtained a TimeMap for google.com from our locally deployed Memento
aggregator (MemGator instance) containing 714,470 URI-Ms from 8 different
Memento-compliant archives. Table 1 shows the distribution of the mementos
using a simple URI-based association algorithm to attribute URI-Ms to an
archive. 89.1% of the URI-Ms returned were from Internet Archive.

###  5.1. Variation in Scheme

Two schemes (Fielding and Reschke, 2014a) are used for the URI-Rs contained
within the URI-Ms returned: HTTP and HTTPS. Table 2 shows the breakdown of the
URI-Rs contained in the URI-Ms based on the TimeMap, inclusive of the inferred
URI-Rs whose scheme could not be determine solely from the URI-M. As discussed
in Section 2.4, the more accurate method to attribute a URI-R to a URI-M is to
obtain the memento’s “original” Link header values but this section focuses on
analyzing the contents of the TimeMap without requesting the URI-Ms.

From the URI-Rs that could be extracted, 86.2% used the HTTP scheme. Table 3
shows the URI-R-based memento count for each scheme using a substring-based
grouping approach similar to that used for Table 1. The TimeMap contained
canonicalized variants of the URI-Rs embedded as substrings within the URI-Ms
with our query for the CDXJ-formatted TimeMap. Our query supplied the URI-R
variant containing the HTTP scheme, www sub-domain, and no trailing characters
combination (i.e., http://www.google.com) via the query to
MemGator555http://localhost:1208/timemap/cdxj/http://www.google.com.

Scheme | URI-R count
---|---
http | 609,274
https | 97,645
unknown | 7,551
| 714,470
Table 2. Scheme distribution among the URI-Rs within the mementos in the
TimeMap for google.com. Figure 4. The average time between consecutive
mementos has decreased with time. This plot shows a year-based bucketing of
the difference in time between adjacent mementos from different archives for
google.com.

###  5.2. Grouping by Year

We separated the URI-Ms as reported by the TimeMap into year-based buckets
using the “datetime” attribute for each URI-M (and not the embedded 14-digit
date stamp per Section 2.4) as well as by-archive for google.com. We
calculated the average time between URI-Ms within a year-based bucket to show
that the velocity of capturing google.com is generally increasing in time
(Figure 4). The quantity of captures from Internet Archive for google.com in
2015 was significantly lower than the trend would indicate. Table 4 indicates
this dramatic drop in google.com captures from both the IA CDX endpoint and
from the Memento endpoint. Also because data collection occurred in May 2016,
the partial year data points for 2016 are on-par with the trend of years prior
to 2015.

Scheme | Format |  URI-R count
---|---|---
http | http://www.google.com | 541,160
| http://google.com | 67,811
| http://other.google.com | 303
https | https://www.google.com | 96,853
| https://google.com | 792
| https://other.google.com | 0
Table 3. Count of URI-Rs contained within URI-Ms for google.com.

year | MTM | MRC | $DI$
---|---|---|---
1998 | 4 | 4 | $\infty$
1999 | 19 | 19 | $\infty$
2000 | 132 | 87 | 1.933
2001 | 1,185 | 579 | 0.955
2002 | 176 | 137 | 3.513
2003 | 75 | 55 | 2.750
2004 | 197 | 143 | 2.648
2005 | 1,236 | 414 | 0.504
2006 | 735 | 483 | 1.917
2007 | 1,055 | 842 | 3.953
2008 | 1,376 | 894 | 1.855
2009 | 6,074 | 4,335 | 2.493
2010 | 9,326 | 6,530 | 2.335
2011 | 20,634 | 9,279 | 0.817
2012 | 102,533 | 16,240 | 0.188
2013 | 228,405 | 25,203 | 0.124
2014 | 164,865 | 22,738 | 0.160
2015 | 17,978 | 11,286 | 1.686
2016 | 139,520 | 5,805 | 0.043

Table 4. Google over time, bucketed by year, based on IA mementos extracted
from the MemGator CDXJ TimeMap. MTM is the memento count based solely on the
data in the TimeMap, MRC is the count based on exclusion of redirects when
dereferenced, and $DI$ is the ratio of non-redirecting mementos to redirecting
mementos, per Section 6.3.

.

###  5.3. “TimeMap” from CDX Server

We also obtained the CDX for google.com from Internet Archive (IA). We
compared the HTTP response codes we received when dereferencing the IA URI-Ms
from the CDXJ TimeMap (Section 4) with the response codes explicitly provided
in the CDX listing IA returned. Per Section 2.2, a CDX endpoint is not
available as a user-accessible endpoint from most Web archives. We used the
available endpoint at IA as a sanity check for correctness of the data
obtained when the URI-Ms in a TimeMap are dereferenced. The intention of
analyzing the TimeMap and not simply deferring to the CDX Server, despite the
majority of mementos in the aggregated TimeMap being from IA, is to
extrapolate the dereferencing strategy to other Memento-compliant Web
archives.

##  6\. Analysis based on Mementos

In Section 5 we analyzed the archival presence of a URI based solely on the
TimeMap supplied by a local aggregator when querying the aggregator with one
canonicalized variant of the URI-R. In this section, we dereference the URI-Ms
in the TimeMap for further analysis. Equations 1 and 2 set the basis for
counting mementos in a TimeMap by merely counting the entries where the “rel”
attribute in a TimeMap contains a value of “memento”. For example, Figure 1
shows a Link formatted TimeMap where each highlighted entry containing a
“memento” rel value (with the potential additional inclusion of other values
like “last” and “first”) increments the count according to Equation 2.

(1) $M=\text{URI-M}\subset\text{TimeMap},\text{if}\
``memento"\subset\text{valuesOf(}rel\text{)}\\\ $ (2)
$|TM|_{rel}=\sum_{m=1}^{len(M)}1$

###  6.1. Redirects in Mementos

The number of non-redirecting (non-3XX) mementos in a TimeMap cannot be
counted with the TimeMap data alone. When URI-Ms are dereferenced, they need
not contain an entity body but may consist only of an archived HTTP response,
which might not be a 200. This occurs in cases where the live Web site
returned an HTTP 302 redirect, among other circumstances. This redirect was
captured, retained, and is replayed by the archives. When replayed, the
datetime originally requested for a URI-R, as is often the case, will be
different than the datetime of the memento ultimately served to the user. This
“archived 302” is different from a 3XX code returned from an archive that is
not representative of an archival capture; for example, when a datetime for a
URI is requested where no capture for the URI is contained within the
archive’s holdings.

Assuming the TimeMap in Figure 1 is wholly inclusive of all of the mementos
contained by Internet Archive for example.com, requesting the URI-M
http://web.archive.org/web/20160728114743/http://www.example.com (two seconds
before a listed URI-M neglecting datetime semantics per Section 2) will result
in a 302 from the archive pointing to the nearest capture. This behavior is a
function of the archive, is not mandatory behavior to exhibit, and is
functionality independent of the Memento protocol. Were there a capture at the
former datetime where the archival crawler experienced a 302 from the live Web
at the time, the TimeMap would contain the URI-M
http://web.archive.org/web/20160728114743/http://www.example.com with a rel
value of “memento” indistinguishable from the memento entry at
http://web.archive.org/web/20160728114743/http://www.example.com regardless of
the status code that occurs from the archive when each URI-M is dereferenced.

###  6.2. Direct and Indirect Mementos

Users interacting with an archive via a Web browser will not directly
experience intermediary HTTP transactions (the user agent automatically
redirects the user to a non-3XX status), we introduce the term URI-MD (for
“direct”) to indicate a URI-M in a TimeMap that does not require any
intermediary transaction to resolve. Thus, a URI-MD is a case of a URI-M where
the URI-M originally requested by the user is the identifier for the ultimate
memento served. URI-Ms in a TimeMap that exhibit the behavior where a HTTP 3XX
class code is replayed and the datetime differs from that requested by the
user are indicated with URI-MI (for “indirect”).

In Equation 3 we filter $|TM|_{rel}$ from Equation 2 to exclude mementos that
resolve to HTTP 3XX status codes. $|TM|_{D}$ represents the count of mementos
that result in non-3XX statuses based on the URI-Ms in a TimeMap. Section
2.2.4 of the Memento RFC (Van de Sompel et al., 2013) states that a link with
a datetime attribute must match the value of the Memento-Datetime header when
the link is dereferenced.

(3) $|TM|_{D}=\sum_{m=1}^{len(M)}\begin{cases}0\ &300\geq
httpStatus(m)<400,\\\ 1\ &\text{otherwise.}\end{cases}$

(4) $|TM|_{I}=|TM|_{rel}-|TM|_{D}$

We quantify the ratio of mementos with non-redirecting HTTP status codes
(Equation 3) to those with redirects (Equation 4) in Equation 5 as $DI$.

(5) $DI=\begin{cases}\frac{|TM|_{D}}{|TM|_{I}}\ &|TM|_{I}>0,\\\
\infty&\text{otherwise.}\end{cases}$

As an example, Figure 5 contains 11 URI-Ms that result in non-redirecting
archived HTTP status codes when dereferenced, inclusive of eight 200 codes,
two 4XX codes, and one archived 504. TimeMap A represents a domain for an
organization (for example) that is acquired by another organization, whose
domain is represented by TimeMap B. At the point of acquisition, TimeMap A
redirects to TimeMap B, as represented by the HTTP 301. At two points prior to
acquisition, an archival crawler attempted to capture the URI-R for TimeMap A
but received a server-side redirect, which is reflected in the preserved HTTP
302 responses. As the acquisition proceeded, the URI-R may have been deleted
(the 404 in TimeMap A) and the server misconfigured in the transition (HTTP
504). An intermittent HTTP 401 (Unauthorized) error is also experienced in the
URI-R for TimeMap B as the servers are reconfigured to accept the additional
traffic from the acquisition.

Figure 5.  Dereferencing URI-Ms in a TimeMap may produce a variety of HTTP
status code, some of which are redirects both to other URI-Ms within the
TimeMap and URI-Ms not included in the initial TimeMap. Counting the number of
mementos without dereferencing URI-Ms is therefore problematic.

Three URI-Ms resulted in 3XX redirects when dereferenced. Using Equation 5,
$DI=11/3\approx 3.7$. Sparsely archived URIs will often contain a list of URI-
Ms where all result in an HTTP 200 status code when dereferenced, which would
result in $DI$ being undefined. It is far less likely that all URI-Ms in a
TimeMap return in an HTTP redirect when dereferenced.

During the data acquisition process (Section 4) we experienced intermittent
HTTP 5XX status codes (Fielding and Reschke, 2014b) in responses from Internet
Archive, namely HTTP 503 (Service Unavailable) and 504 (Gateway Timeout). In
much of the same way that sending an Accept-Datetime header causes a “soft”
HTTP status code to “harden”, we repeated the request via
curl666https://curl.haxx.se/ with the inclusion of an Accept-Datetime HTTP
header (Van de Sompel et al., 2013). This additional step caused no change in
the subsequently returned results compared to the originally results response.
Repeating the collection procedure for select URI-Ms in the future remedied
this issue, allowing us to attribute the error to the archive and not the
archive returning a capture of an archived 5XX. If the response instead
indicated that the returned 5XX status codes was representative of the state
of the URI-R at the respective time (through providing a Memento-Datetime
response header) and not an intermittent result attributable to the archive,
the URI-M would signify an increment in the Equation 3 summation.

###  6.3. Canonicalization Patterns

In observing the mementos for http://www.google.com, we encountered 3
canonicalization patterns for URI-Ms that surface those that are URI-MD versus
those that are URI-MI. We define $M_{TM}$ to be the memento count for a
TimeMap when using only the data contained in the TimeMap without
dereferencing mementos (Section 5). We define the representative count
($M_{RC}$) of the number of mementos present in a TimeMap to be the number of
URI-MD where $M_{RC}\leq M_{TM}$. These canonicalization patterns observed are
Inter-scheme, Slash-added, and subdomain redirect patterns, described in this
section.

⬇

<http://google.com>; rel="original",

…

$M_{1}$<http://web.archive.org/web/20011124163711/http://www2.google.com/>;
rel="memento"; datetime="Sat, 24 Nov 2001 16:37:11 GMT",

…

$M_{2}$<http://web.archive.org/web/20130101000813/http://www.google.com/>;
rel="memento"; datetime="Tue, 01 Jan 2013 00:08:13 GMT",

$M_{3}$<http://web.archive.org/web/20130101003310/https://www.google.com/>;
rel="memento"; datetime="Tue, 01 Jan 2013 00:33:10 GMT",

…

$M_{4}$<http://web.archive.org/web/20140425221431/http://www.google.com>;
rel="memento"; datetime="Fri, 25 Apr 2014 22:14:31 GMT",

$M_{5}$<http://web.archive.org/web/20140425221433/https://www.google.com/>;
rel="memento"; datetime="Fri, 25 Apr 2014 22:14:33 GMT",

…

$M_{6}$<http://web.archive.org/web/20160519223823/http://www.google.com/>;
rel="memento"; datetime="Thu, 19 May 2016 22:38:23 GMT",

$M_{7}$<http://web.archive.org/web/20160520165954/http://google.com/>;
rel="memento"; datetime="Fri, 20 May 2016 16:59:54 GMT",

…

Figure 6. A partial TimeMap in Link format for google.com with annotations
highlighting various URI-Ms, discussed in Section 6.3.

####  6.3.1. Inter-scheme URI-M Redirect

As adoption of the secure HTTPS scheme over HTTP becomes more prevalent on the
live Web (Robinson and Timm, 2015; Podjarny, 2016), the trend becomes apparent
in the archives through canonicalizing the HTTP and HTTPS site to be one in
the same. For example, observe two mementos from 2013 from the TimeMap for
google.com (Figure 6). The status code returned for $M_{2}$ is 200 with no
HTTP location header present (an example of a URI-MD). However, the status
code returned for $M_{3}$ is an HTTP 302 with an HTTP location response header
of /web/20130101000813/http://www.google.com/, i.e., $M_{3}$ redirects to
$M_{2}$ when dereferenced. Thus, $M_{3}$ is a URI-MI. Were the naive but often
applied Equation 2 used for determining how many mementos are represented by
the URI-Ms $M_{2}$ and $M_{3}$, both would be included while dereferencing
each URI-M would result in a count of only a single memento. This highlights
an important distinction and discrepancy between the number of identifiers
(URI-Ms) and the number of representations (mementos).

####  6.3.2. Slash-added URI-M Redirect

Queries for the URI http://www.google.com are sometimes redirected to the same
URI with an appended slash. For example, the two mementos $M_{4}$ and $M_{5}$
both exist in a TimeMap (Figure 6).

When dereferenced, $M_{4}$ returns a 302 with a location header pointing to
$M_{5}$, captured two seconds later based solely on the embedded datetime.
Both URI-Ms are reported by the TimeMap while only the latter contains an
entity body when dereferenced.

Time Gap Bucket | URI-M count
---|---
0 seconds | 24,541
1 second | 34,577
2 seconds | 26,153
3 seconds | 62,526
4 seconds | 46,738
5 seconds | 14,215
6 seconds | 12,213
7 seconds | 9,748
8 seconds | 7,431
9 seconds | 6,610
$>$ 9 seconds, $\leq$ 1 minute | 101,868
$>$ 1 minute, $\leq$ 1 hour | 247,192
$>$ 1 hour, $\leq$ 1 day | 37,399
$>$ 1 day | 5,034
Table 5. A range of time differences exists between adjacent captures of a
URI-R. This table represents the instances of these differences between
adjacent URI-Ms from the TimeMap for google.com reported by Internet Archive.

####  6.3.3. Subdomain URI-M Redirect

It is also useful to observe canonicalization that does not result in a
redirect. Google has used a variety of subdomains of the sort containing the
literal “www” followed by a digit over the years, as with $M_{1}$ (Figure 6).
Accessing this memento (dereferencing $M_{1}$) results in an HTTP 200 status
code. The other, much more common subdomain of www, as with $M_{6}$ returns an
HTTP 302 redirected to $M_{7}$, both present in the TimeMap. Table 7(a) shows
the magnitude of redirects for google.com based on the URI-Rorig scheme, URI-
Rorig subdomain, URI-Rdest scheme, and URI-Rorig subdomain. The breakdown in
Table 7(a) was also generated for comparison to the URI-Rs vimeo.com and
wikipedia.org in Tables 7(b) and 7(c), respectively.

####  6.3.4. Analysis

Juxtaposing the proportion exhibited for each of the four permutations of
scheme transitions (HTTP-to-HTTP, HTTP-to-HTTPS, etc.) from vimeo.com and
wikipedia.org as compared to google.com, the inter-scheme transition seems
more common with the former pair while the bulk of the results for google.com
reside in redirects that retain both the HTTP scheme in the URI-R but also the
www subdomain. Focusing specifically on the HTTP-to-HTTPS inter-scheme
transition, Figure 7 serves as an interesting cross-section of Table 7(a)
broken down by time. Disregarding the anomalous captures from Internet Archive
in 2015, the overall trend of inter-scheme redirects is leaning toward more
HTTP-to-HTTPS than HTTPS-to-HTTP as the secure scheme is adopted by more sites
on the live Web. Disregarding 2015, the HTTP-to-HTTPS redirects for vimeo.com
appear to be monotonically increasing with normalization for the partial year
results for 2016 (collection was performed in May of that year). Figure 7 also
shows a steeper quantity of captures containing these redirects for
wikipedia.org with few captures of redirects exhibiting this inter-scheme
permutation prior to 2014. The rapid increase in each site may temporally
correspond with the adoption of the HTTPS scheme by the live Web site, thereby
forwarding all traffic accessing the HTTP version of the site using an HTTP
3XX response.

An additional nuance to account for the large quantity of redirects from HTTP
URI-Ms to HTTP URI-Ms for google.com can be observed by the large quantity of
“revisit” entries in IA’s CDX results for google.com. A revisit entry occurs
when an archival crawler is returned content that is identical to a previous
capture, often attributed using a hashing scheme on the live page’s content.
If an archive reports revisit records as an HTTP redirect based on the CDX
listing, and this redirect is propagated to the archive’s Memento endpoint
thus producing a unique URI-M, the $DI$’s value for the URI-R decreases.
Requesting the URI-M using the Accept-Datetime HTTP header then observing the
Memento-Datetime response header’s presence often reveals this nuance, but by
relying on the TimeData data without requesting each URI-M , the $DI$ for the
URI-R is unknown.

Year | Memento count
---|---
2001 | 68
2005 | 391
2006 | 8
2007 | 81
2008 | 62
2009 | 153
2010 | 124
2011 | 616
2012 | 5,564
2013 | 25,914
2014 | 40,819
2015 | 1,367
2016 | 10,104
Table 6. Google memento analysis group by memento year where the time between
two mementos is less than or equal to 2 seconds.

###  6.4. Inter-Memento Temporality

We measured the time between each pair of consecutive mementos, shown in Table
5. We found that 38.4% had a time gap less than 9 seconds, indicating (in some
cases) that a redirect would occur when the URI-M is dereferenced. Using a
yearly bucketing scheme (Table 10), we plotted the difference in time between
adjacent mementos from IA based on the scheme in the URI-MI and the ultimate
URI-M that results when the URI-MI is dereferenced. For each log-log plot,
shown with more details in the Appendix, a point’s quadrant positioning is
indicative of the quantity of mementos with a seconds-level granularity of
time. For example, a point in the top-left quadrant of a plot indicates that
there are many temporally consecutive memento pairs with a very small time
difference between them. Top right would indicate many pairs with a large time
difference between them; bottom right: few memento pairs with a large time
difference; bottom left: few memento pairs with a small time difference. Many
more points in the left half of a plot than the right indicates much less time
between captures, i.e., the capture frequency was higher that year. More
points being in the right half of the plot indicates that more time passes
between consecutive captures. The trend for google.com excluding 2015 shows
fewer pairs with a small time difference (more points in the bottom right) as
time goes on for all redirect patterns other than HTTP-to-HTTP.

Figure 7. Inter-scheme redirects for google.com, vimeo.com, and wikipedia.org
from the mementos in the TimeMap from MemGator for IA that result in a 3XX.

###  6.5. Temporal Closeness as an Indicator of Redirection

In only brief examination of the TimeMap, some temporally consecutive URI-Ms
appeared in “pairs” where a second URI-M exists from the same archive within
seconds of the previous. Table 6 lists the by-year breakdown filtering to only
include the URI-Ms where the time between the two is less than two seconds.
The trend generally increases with time. This plot can also be cross-
referenced with Table 7(a), which shows the overall inter-scheme redirect
breakdown totals independent of time with the additional subdomain
granularity.

Table 6 also shows a peak in 2014 at 40,819 pairs where the redirect is less
than or equal to two seconds apart from the URI-Rorig to the URI-Rdest. Given
the quantity of inter-scheme redirects in Figure 7 for 2014 totaling around
30,000 as the sum and Table 7(a) showing a significantly larger number of same
scheme redirects (e.g., 490,836 just for HTTP-to-HTTP both with the www
subdomain), many redirects over the archived history of google.com can be
attributed to something other than a scheme switch. The large number of
aforementioned identical scheme and subdomain redirects indicates patterned
responses like slash-added (Section 6.3.2) rather than scheme (Section 6.3.1)
or subdomain switch (Section 6.3.3).

URI-Rorig scheme URI-Rdest scheme |  | http | https
---|---|---|---
http |  | none | www | other | none | www | other
none | 1,279 | 68,837 | 55 | 12 | 20,825 | 27
www | 8,934 | 490,836 | 204 | 32 | 77,610 | 16
| other | 0 | 224 | 22 | 0 | 26 | 2
https | none | 14 | 731 | 0 | 0 | 296 | 1
www | 1,117 | 72,874 | 27 | 15 | 18,525 | 2,101
other | 0 | 0 | 0 | 0 | 0 | 0
(a) Scheme and subdomain for redirects when dereferencing URI-Ms for
google.com.

URI-Rorig scheme URI-Rdest scheme |  | http | https
---|---|---|---
http |  | none | www | other | none | www | other
none | 1,642 | 104 | 0 | 82,637 | 0 | 0
www | 1,273 | 50 | 0 | 6,355 | 0 | 0
| other | 0 | 0 | 0 | 0 | 0 | 0
https | none | 315 | 6 | 0 | 35,293 | 1 | 0
www | 10 | 0 | 0 | 1,149 | 0 | 0
other | 0 | 0 | 0 | 0 | 0 | 0
(b) Scheme and subdomain for redirects when dereferencing URI-Ms for
vimeo.com.

URI-Rorig scheme URI-Rdest scheme |  | http | https
---|---|---|---
http |  | none | www | other | none | www | other
none | 91 | 10,575 | 0 | 0 | 4,140 | 0
www | 110 | 5,099 | 0 | 1 | 44,104 | 0
| other | 0 | 0 | 0 | 0 | 0 | 0
https | none | 1 | 46 | 0 | 1 | 804 | 0
www | 14 | 1,014 | 0 | 0 | 5,602 | 0
other | 0 | 0 | 0 | 0 | 0 | 0
(c) Scheme and subdomain for redirects when dereferencing URI-Ms for
wikipedia.org.

Table 7. When URI-Ms for three select domains (google.com, vimeo.com, and wikipedia.org), are dereferenced and produce an HTTP redirect, the originally accessed URI-Rorig can result in a URI-Rdest with a different scheme and subdomain. Cell colors correspond to lines in Figure 7. The scheme and subdomain is “Unknown” for URI-Ms (like those from webcitation) that obfuscate URI-R with which the URI-M is associated. See Section 2. host | % 3XX | % 200 | MTM | $DI$
---|---|---|---|---
google | 84.89 | 15.11 | 695,525 | 0.178
yahoo | 88.16 | 11.83 | 418,896 | 0.134
sourceforge | 73.34 | 26.63 | 31,408 | 0.363
instagram | 67.32 | 32.65 | 55,228 | 0.485
vimeo | 57.04 | 42.94 | 199,262 | 0.752
cnn | 49.97 | 50.01 | 87,148 | 1.001
wikipedia | 44.62 | 55.19 | 25,973 | 1.240
whitehouse | 44.57 | 55.24 | 26,006 | 1.243
Table 8. Dereferencing 7 other large Web sites’ TimeMaps from Internet Archive
produces the above distribution of status codes for each site.

###  6.6. Beyond Google

We then evaluated the applicability of the observations for google.com with
other archived Web sites. We dereferenced the TimeMaps of 7 additional large
Web sites (Table 8) with a variety of adoption trends of HTTPS and
ephemerality as well as 13 home pages of various universities and colleges
(Table 9). From this further analysis, we observed how prevalent the trend is
as exhibited by google.com with a hypothesis that the relatively static,
fundamentally unchanging Google homepage is a reason for the relatively low
$DI$.

Figure 8. Nine URI-Rs from Tables 8 and 9 exhibit different degrees of
redirection over time.

For the select academic institutions in Table 9, $DI$ is inversely proportion
to MTM, albeit not strictly as evidenced by “gatech” and “odu”. This pattern
does not generally hold in comparison to the large sites in Table 8 though the
selection of sites for each may contain some inadvertent bias. Figure 8 shows
nine plots representing the percentage of redirects over time as determined
when all URI-Ms with a rel value in the respective TimeMaps from IA are
dereferenced.

host | % 3XX | % 200 | MTM | $DI$
---|---|---|---|---
stanford | 62.14 | 37.84 | 19,309 | 0.609
princeton | 60.10 | 39.88 | 9,355 | 0.663
columbia | 48.01 | 51.88 | 9,882 | 1.082
harvard | 33.91 | 65.96 | 7,699 | 1.948
caltech | 33.13 | 66.86 | 5,474 | 2.017
mit | 26.57 | 73.24 | 6,379 | 2.763
gatech | 26.03 | 73.94 | 3,907 | 2.841
ufl | 24.76 | 75.23 | 4,927 | 3.038
vt | 23.07 | 76.92 | 4,061 | 3.334
lsu | 15.06 | 84.93 | 2,974 | 5.638
nsu | 13.82 | 86.00 | 1,208 | 6.233
odu | 9.727 | 90.27 | 1,727 | 9.279
tcc | 5.429 | 94.57 | 884 | 17.41
Table 9. Dereferencing the TimeMaps from 13 academic institutions’ Web sites from Internet Archive produces the above distribution of status codes for each site. year | scheme${}_{orig}\rightarrow$schemedest
---|---
http$\rightarrow$http | http$\rightarrow$https | https$\rightarrow$http | https$\rightarrow$https
2010 |  |  |  |
2011 |  |  |  |
2012 |  |  |  |
2013 |  |  |  |
2014 |  |  |  |
2015 |  |  |  |
2016 |  |  |  |
Table 10. Count of time delta instances for google.com from IA TimeMaps with
3XX redirects. Highlighted columns correspond to Figures 7(a) and 7.The plots
in this Figure are available with more detail in the Appendix.

##  7\. Conclusions

In this work we identified the problem of attempting to count the number of
mementos in a TimeMap based solely on the contents of the TimeMap. We
progressively built a method for counting the number of archived captures of
Web pages that contain content when dereferenced from a TimeMap. Through
observing google.com, a URI-R with a contemporarily large apparent number of
mementos, we dereferenced all URI-Ms in an aggregated TimeMap for the URI-R to
show that a 84.9% of the URI-Ms are redirects to other URI-Ms in the TimeMap.

We establish the nomenclature of MRC, a means of communicating the number of
URI-Ms in a TimeMap that contain a capture with an entity body, as compared to
the more naive MTM as calculated using solely the contents of the TimeMap for
a URI-R. We analyzed the TimeMaps for the URI-Rs of seven other contemporary
large web sites and the TimeMaps from 13 academic institutions. We introduced
the $DI$ metric to evaluate the ratio of non-redirecting URI-Ms in a TimeMap
to the ratio of redirecting URI-Ms when all URI-Ms in a TimeMap are
dereferenced. Five of the eight large Web sites’ URI-Rs and two of the
thirteen academic institutions’ URI-Rs contained more redirecting than non-
redirecting mementos when dereferenced ($DI<1.0)$.

From the URI-Ms for google.com that redirected, we split the results between
those that changed schemes and those that maintained the same URI-R scheme
after the redirect. We split the results on an annual basis to show the effect
that the introduction of HTTPS has had on URI-R canonicalization over time. We
found that despite an anomalous set of captures in the year 2015, the number
of redirects per year on the live Web from HTTP URI-Rs to HTTPS URI-Rs as
preserved by the archive has superseded the number of redirects of HTTPS URI-
Rs to HTTP URI-Rs. Though the quantity of holdings by Internet Archive for
redirects from HTTPS to HTTP is not yet larger than the total of other
permutations of HTTP(S) to HTTP(S) redirects (Table 7(a)), the rapid growth of
redirects to the secure scheme for captures confirms and quantifies the
increased adoption of HTTPS on the live Web.

## References

  * (1)
  * Alam and Nelson (2016) Sawood Alam and Michael L. Nelson. 2016.  MemGator - A Portable Concurrent Memento Aggregator. In Proceedings of the 16th ACM/IEEE-CS on Joint Conference on Digital Libraries (JCDL). 243–244.  DOI:http://dx.doi.org/10.1145/2910896.2925452
  * Alam et al. (2015) Sawood Alam, Michael L. Nelson, Herbert Van de Sompel, Lyudmila Balakireva, Harihar Shankar, and David S. H. Rosenthal. 2015.  Web Archive Profiling Through CDX Summarization. In Proceedings of Theory and Practice of Digital Libraries (TPDL). 3–14.  DOI:http://dx.doi.org/10.1007/s00799-016-0184-4
  * AlSum et al. (2013) Ahmed AlSum, Robert Sanderson, Herbert Van de Sompel, and Michael L. Nelson. 2013.  Archival HTTP Redirection Retrieval Policies. In Proceedings of the Third Temporal Web Analytics Workshop.  DOI:http://dx.doi.org/10.1145/2487788.2488117
  * Bar-Yossef et al. (2004) Ziv Bar-Yossef, Andrei Z. Broder, Ravi Kumar, and Andrew Tompkins. 2004.  Sic Transit Gloria Telae: Towards an Understanding of the Web’s Decay. In Proceedings of the 13th International Conference on World Wide Web (WWW). 328–337.  DOI:http://dx.doi.org/10.1145/988672.988716
  * Fielding and Reschke (2014a) R. Fielding and J. Reschke. 2014a.  Hypertext Transfer Protocol (HTTP/1.1): Message Syntax and Routing, Internet RFC-7230.  (2014).
  * Fielding and Reschke (2014b) R. Fielding and J. Reschke. 2014b.  Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content, Internet RFC-7231.  (2014).
  * Jacobs and Walsh (2004) Ian Jacobs and Norman Walsh. 2004.  Web Architecture : URI Opacity.  https://www.w3.org/TR/webarch/#uri-opacity. (2004).  https://www.w3.org/TR/webarch/#uri-opacity
  * Jordan et al. (2015) Wesley Jordan, Mat Kelly, Justin F. Brunelle, Laura Vobrak, Michele C. Weigle, and Michael L. Nelson. 2015.  Mobile Mink: Merging Mobile and Desktop Archived Webs . In Proceedings of the ACM/IEEE Joint Conference on Digital Libraries (JCDL). 243–244.  DOI:http://dx.doi.org/10.1145/2756406.2756956
  * Kelly et al. (2014) Mat Kelly, Michael L. Nelson, and Michele C. Weigle. 2014\.  Mink: Integrating the Live and Archived Web Viewing Experience Using Web Browsers and Memento. In Proceedings of the IEEE/ACM Joint Conference on Digital Libraries (JCDL). 469–470.  DOI:http://dx.doi.org/10.1109/JCDL.2014.6970229
  * Meneses et al. (2012) Luis Meneses, Richard Furuta, and Frank Shipman. 2012\.  Identifying “Soft 404” Error Pages: Analyzing the Lexical Signatures of Documents in Distributed Collections. In Proceedings of the International Conference on Theory and Practice of Digital Libraries (TPDL). 197–208.  DOI:http://dx.doi.org/10.1007/978-3-642-33290-6_22
  * Nelson (2013) Michael L. Nelson. 2013\.  Wayback Machine Upgrades Memento Support.  http://ws-dl.blogspot.com/2013/07/2013-07-15-wayback-machine-upgrades.html. (September 2013).
  * Ohye and Kupke (2012) M. Ohye and J. Kupke. 2012\.  The Canonical Link Relation, Internet RFC-6596.  (2012).
  * Podjarny (2016) Guy Podjarny. 2016\.  HTTPS Adoption *doubled* this year | Snyk.  (July 2016).  https://snyk.io/blog/https-breaking-through/ [Online; accessed 21-January-2017].
  * Robinson and Timm (2015) Garrett Robinson and Trevor Timm. 2015.  Introducing Secure The News, an automated tool tracking the adoption of HTTPS encryption across news websites.  (December 2015).  https://freedom.press/news/introducing-secure-news-automated-tool-tracking-adoption-https-encryption-across-news-websites/ [Online; accessed 21-January-2017].
  * Rosenthal (2013) David S. H. Rosenthal. 2013\.  Re-thinking Memento Aggregation.  http://blog.dshr.org/2013/03/re-thinking-memento-aggregation.html. (March 2013).
  * Van de Sompel et al. (2013) Herbert Van de Sompel, Michael Nelson, and Robert Sanderson. 2013\.  HTTP Framework for Time-Based Access to Resource States – Memento.  IETF RFC 7089. (December 2013).

##  Appendix A Detailed plots from Table 10


# A ride time-oriented scheduling algorithm for dial-a-ride problems

Claudia Bongiovanni
Polytechnique Montréal and CIRRELT
<EMAIL_ADDRESS>&Nikolas Geroliminis
École Polytechnique Fédérale de Lausanne
<EMAIL_ADDRESS>&Mor Kaspi
Tel-Aviv University
<EMAIL_ADDRESS>
###### Abstract

This paper offers a new algorithm to efficiently optimize scheduling decisions
for dial-a-ride problems (DARPs), including problem variants considering
electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based
on linear programming theory, aims at finding minimal user ride time schedules
in polynomial time. The algorithm can either return optimal feasible routes or
it can return incorrect infeasibility declarations, on which feasibility can
be recovered through a specifically-designed heuristic. The algorithm is
furthermore supplemented by a battery management algorithm that can be used to
determine charging decisions for electric and autonomous vehicle fleets.
Timing solutions from the proposed scheduling algorithm are obtained on
millions of routes extracted from DARP and e-ADARP benchmark instances. They
are compared to those obtained from a linear program, as well as to popular
scheduling procedures from the DARP literature. Results show that the proposed
procedure outperforms state-of-the-art scheduling algorithms, both in terms of
compute-efficiency and solution quality.

_K_ eywords scheduling $\cdot$ routing $\cdot$ battery management $\cdot$
dial-a-ride $\cdot$ heuristics

##  1 Introduction

Many real-world urban mobility and supply chain problems involve time-
dependent allocation and sequencing decisions that must be frequently re-
optimized over time. The re-optimization process is typically composed of the
production and evaluation of a plethora of potential solutions. The evaluation
of these solutions is performed by scheduling algorithms, whose goals are to
determine the timing of the sequential decisions, while respecting several
time-related constraints and objectives (e.g., Vidal et al. 2015). Their
efficient resolution is particularly relevant for large-scale and dynamic
problems, since in these cases scheduling decisions must be made frequently
and quickly, as for example in the context of large neighborhood search
methods (e.g., Gschwind and Drexl 2019). In addition to computational
efficiency, it is essential that scheduling algorithms provide high-quality
solutions, given their direct impact on the quality of allocation decisions
and thus on the overall performance of the optimization strategy.

Scheduling algorithms are of utmost importance for hardly-constrained vehicle
routing problems. They assume feasible vehicle routes in terms of capacity and
precedence constraints and are designed to provide feasible decisions on time-
related variables (e.g., service start times and waiting times at each node).
Demonstrating the feasibility of a fixed route and composing high-quality
vehicle schedules is a challenging task for most vehicle routing problems
because of the presence of time-related constraints (e.g., time windows and
maximum route duration). For dial-a-ride (DARP) problems, this task is made
even more challenging by the presence of constraints on maximum user ride time
(Cordeau and Laporte 2007), as well as constraints on battery management and
charging time for fleets composed of electric and autonomous vehicles
(e-ADARP, Bongiovanni et al. 2019, Yue et al. 2022, 2023). Consequently, the
goal of some scheduling algorithms for DARPs is optimize time dependent level
of service while satisfying several time related constraints. The former is
often measured by the user excess ride time, that is the delay users
experience for sharing rides as compared to a taxi service (e.g., see Section
3 in Molenbruch et al. 2017a).

A variety of heuristics have been proposed in the DARP literature to manage
path planning. However, these procedures typically face a trade-off between
returning correct feasibility declarations and increasing the quality of the
returned solutions. Cordeau and Laporte (2003) propose an 8-step procedure
setting the earliest start time at each vertex in the route and using forward
slack times to delay the start times at pickup locations in vision of maximum
ride time constraints (Savelsbergh 1992). Parragh et al. (2009) observe that
adopting a sequential approach to avoid maximum ride time violations does not
necessarily minimize the total user excess ride time in the schedules. In
fact, delaying the service start time at a given pickup location may decrease
the excess ride time of the specific request but increase the excess ride time
for other requests in the route. As such, Parragh et al. (2009) modify the
procedure in Cordeau and Laporte (2003) by adapting the computation of forward
slack times such that increases in the user excess ride time of any request in
the route is avoided. As a result, the returned feasible schedules minimize
the total user excess ride time at the expense of incorrect infeasibility
declarations. This last aspect is a drawback that is tackled in Molenbruch et
al. (2017b), who propose a procedure starting by considering a possibly
travel-time infeasible schedule setting the excess ride time of each user at
its lowest bound. Infeasibility relates to travel time shortages between
successive nodes and is succesively recovered by shifting service start times
such that the total user excess ride time is minimized.

In this work, we propose a novel scheduling heuristic which is numerically
shown to provide excess-time optimal solutions in most cases, although it may
result with incorrect infeasibility declarations or suboptimal solutions. The
designed algorithm is complemented by a battery management heuristic to deal
with DARP extensions employing electric autonomous vehicles, i.e., e-ADARPs.
The goal of the battery management heuristic is to assign charging times at
the visited stations. Indeed, a schedule minimizing excess ride time may not
be battery feasible, and vice versa. The procedure builds on two main
observations:  (i) minimizing excess-time while respecting time-window and
user-ride-time constraints is in fact equivalent to assigning the right amount
of waiting time at all nodes in the routes; and  (ii) ensuring battery
feasibility is in fact possible by recharging as much as possible at the
visited facilities, as early as possible. The proposed scheduling and battery
management algorithms are tested on millions of DARP and e-ADARP routing
solutions obtained by developing an adaptive large neighborhood search
heuristic (Ropke and Pisinger 2006). The quality of the obtained scheduling
solutions are compared against:  (i) a linear program;  (ii) the well-known
8-step scheduling procedures by Cordeau and Laporte (2003) and Parragh et al.
(2009); and  (iii) the procedure by Molenbruch et al. (2017b).

The rest of the paper is organized as follows: Section 2 introduces the
excess-ride-time scheduling problem, Section 3 provides the scheduling
algorithm, Section 4 presents the battery management problem and the heuristic
procedure to provide battery-feasibility. Finally, Section 5 provides
numerical experiments comparing the scheduling algorithm against state-of-the-
art procedures, and Section 6 summarizes the main concepts of this paper and
provides an overlook to future research.

##  2 Scheduling Problem

Consider a predetermined route sequence $\mathcal{I}$ of $M$ nodes, which
includes pickup locations, dropoff locations, and potentially some charging
stations. Without loss of generality, assume that the sequence satisfies
routing constraints, as well as precedence and load constraints. Note that the
given sequence may not necessarily satisfy all timing and battery management
constraints. Then, the optimization problem consists in scheduling the service
start times in the sequence as to minimize the total user excess ride time,
guarantee battery, time window, and maximum ride time feasibility.

Start by considering a specific sub-sequence $\mathcal{\bar{I}}$ of
$\bar{M}\leq M$ nodes, which is one of the derived sub-sequences obtained by
splitting $\mathcal{I}$ by the visited charging stations. Without loss of
generality, assume that the visited charging station at the beginning of
$\mathcal{\bar{I}}$ represents an origin depot and the charging station at the
end of $\mathcal{\bar{I}}$ represents a destination depot. Furthermore, denote
by $i\in\\{1,\ldots,n\\}$ the set of requests contained in sequence
$\mathcal{\bar{I}}$, $P_{i}$ the set of pickups, and $D_{i}$ the set of
dropoffs. Pickup locations are characterized by loads $l_{P_{i}}$ and dropoff
locations by loads $l_{D_{i}}=-l_{P_{i}}$. Furthermore, all locations
$i,j\in\mathcal{\bar{I}}$ feature service times $s_{i}$, direct travel times
$t_{i,j}$, and time windows [$arr_{i}$, $dep_{i}$] limiting the time at which
service may start. Note that, it is possible to set time windows around the
pickup locations and derive the time windows around the corresponding dropoff
locations by means of the maximum ride times $u_{P_{i}}$, and vice versa
(Cordeau and Laporte 2003). The goal is to be able to optimize
$\mathcal{\bar{I}}$ with respect to the total excess ride time by setting
optimal service start times $T_{i}$ with $i\in\\{1,\ldots,\bar{M}\\}$ in
vision of maximum ride time and time window constraints. As such, the
scheduling problem for sub-sequence $\mathcal{\bar{I}}$ can be stated as the
following linear program:

$(LP1)\hskip
5.69046pt\min\sum\limits_{i\in\\{1,\ldots,n\\}}(T_{D_{i}}-T_{P_{i}}-d_{P_{i}}-t_{P_{i},D_{i}})$
(1) $s.t.:$ $T_{i}+t_{i,i+1}+s_{i}\leq T_{i+1}\hskip 14.22636pt\forall
i\in\\{1,2,\ldots,\bar{M}-1\\}$ (2) $T_{D_{i}}-T_{P_{i}}-d_{P_{i}}\leq
u_{P_{i}}\hskip 14.22636pt\forall i\in\\{1,\ldots,n\\}$ (3) $arr_{i}\leq
T_{i}\leq dep_{i}\hskip 14.22636pt\forall i\in\\{1,2,\ldots,\bar{M}\\}$ (4)

where the objective function (1) minimizes the the sum of excess ride times of
all requests in $\mathcal{\bar{I}}$, constraints (2) set the service start
times between consecutive nodes, while constraints (3)-(4) impose maximum ride
time and time window constraints respectively.

Note that time windows [$arr_{i}$, $dep_{i}$] can be tightened in light of the
travel times and service times between consecutive nodes. As such, by
sequentially inspecting the sequence, it is possible to calculate the earliest
time $ET_{i}$ and latest time $LT_{i}$ at which service can start at node $i$
by using the following recursive formulas:

$ET_{i}=\max\\{arr_{i},ET_{i-1}+t_{i-1,i}+s_{i}\\}\hskip 14.22636pt\forall
i\in\\{2,\ldots,\bar{M}\\},ET_{1}=arr_{1}$ (5)
$LT_{i}=\max\\{dep_{i},LT_{i+1}-t_{i,i+1}-s_{i}\\}\hskip 14.22636pt\forall
i\in\\{1,\ldots,\bar{M}-1\\},LT_{\bar{M}}=dep_{\bar{M}}$ (6)

Hence, a tighter formulation to LP1 can be obtained by substituting
constraints (4) with:

$ET_{i}\leq T_{i}\leq LT_{i}\hskip 14.22636pt\forall
i\in\\{1,2,\ldots,\bar{M}\\}$ (7)

Service start time $T_{i}$ at node $i$ depends on the initial departure time
from the depot, the total travel time up to $i$, the total service time spent
serving nodes before $i$, and the total vehicle waiting time up to $i$. That
is:

$T_{i}=T_{1}+\sum\limits_{j=1}^{i-1}t_{j,j+1}+\sum\limits_{j=1}^{i-1}d_{j}+\sum\limits_{j=1}^{i}w_{j}$
(8)

Here, $w_{i}$ denotes the waiting time at node $i$. Note that, service may
start as soon as possible without penalizing the objective function, i.e.
$T_{1}=ET_{1}$. With such representation of service start times, the objective
function (1) can be re-written as follows:

$\min\sum\limits_{i\in\\{1,\ldots,n\\}}(T_{1}+\sum\limits_{j=1}^{D_{i}-1}t_{j,j+1}+\sum\limits_{j=1}^{D_{i}-1}d_{j}+\sum\limits_{j=1}^{D_{i}}w_{j})-(T_{1}+\sum\limits_{j=1}^{P_{i}-1}t_{j,j+1}+\sum\limits_{j=1}^{P_{i}-1}d_{j}+\sum\limits_{j=1}^{P_{i}}w_{j})-d_{P_{i}}-t_{P_{i},D_{i}}=$
$\min\sum\limits_{i\in\\{1,\ldots,n\\}}(\sum\limits_{j=P_{i}}^{D_{i}-1}t_{j,j+1}+\sum\limits_{j=P_{i}}^{D_{i}-1}d_{j}+\sum\limits_{j=P_{i}}^{D_{i}}w_{j}-d_{P_{i}}-t_{P_{i},D_{i}})$
(9)

Since travel times between consecutive nodes and the service times are
deterministic parameters, minimizing the objective function (9) is equivalent
to:

$\min\sum\limits_{i\in\\{1,\ldots,n\\}}\sum\limits_{j=P_{i}+1}^{D_{i}}w_{j}=\min\sum\limits_{i=1}^{\bar{M}}L_{i}w_{i}$
(10)

Where $L_{i}=\sum\limits_{j=1}^{i-1}l_{j}$ represents the vehicle load up to
node $i$.

Equivalent to the re-writing of the objective function, constraints (7) can be
re-defined through (8) as follows:

$\sum\limits_{j=1}^{i}w_{j}\geq
ET_{i}-\sum\limits_{j=1}^{i-1}t_{j,j+1}+\sum\limits_{j=1}^{i-1}d_{j}-ET_{1}\hskip
14.22636pt\forall i\in\\{1,2,\ldots,\bar{M}\\}$ (11)
$\sum\limits_{j=1}^{i}w_{j}\leq
LT_{i}-\sum\limits_{j=1}^{i-1}t_{j,j+1}+\sum\limits_{j=1}^{i-1}d_{j}-ET_{1}\hskip
14.22636pt\forall i\in\\{1,2,\ldots,\bar{M}\\}$ (12)

Note that these constraints provide lower and upper bounds to the total
waiting time amount that needs to be distributed between $i$ and all nodes
preceding $i$. As such, the linear program (LP1) can be equivalently re-
defined as the following linear program:

$(LP2)\hskip 5.69046pt\min\sum\limits_{i=1}^{\bar{M}}L_{i}w_{i}$ (13) $s.t.:$
$\sum\limits_{j=1}^{i}w_{j}\geq
ET_{i}-\sum\limits_{j=1}^{i-1}t_{j,j+1}-\sum\limits_{j=1}^{i-1}d_{j}-ET_{1}\hskip
14.22636pt\forall i\in\\{1,2,\ldots,\bar{M}\\}$ (14)
$\sum\limits_{j=1}^{i}w_{j}\leq
LT_{i}-\sum\limits_{j=1}^{i-1}t_{j,j+1}-\sum\limits_{j=1}^{i-1}d_{j}-ET_{1}\hskip
14.22636pt\forall i\in\\{1,2,\ldots,\bar{M}\\}$ (15)
$\sum\limits_{j=i+1}^{D_{i}}w_{j}\leq
u_{i}-\sum\limits_{j=i}^{D_{i}-1}t_{j,j+1}-\sum\limits_{j=i+1}^{D_{i}-1}d_{j}\hskip
14.22636pt\forall i\in\mathcal{P}$ (16)

Remark that constraints (2) from (LP1) are guaranteed by the definition of
equation (8), which now composes constraints (14) and (15). The right-hand
side of (14) and (15) represent the minimal total waiting time that must be
assigned up to node $i$, and the maximal total waiting time that can be
assigned up to node $i$, without violating the time windows at sucessive nodes
in the sequence. For convenience, denote the right-hand side of constraints
(14) and (15) by $\Delta_{i}$ and $\Theta_{i}$ respectively. Using equations
(5) and (6) we have that $\Delta_{i}\leq\Delta_{i+1}\hskip 5.69046pt\forall
i\in\\{1,2,\ldots,M-1\\}$ and $\Theta_{i}\leq\Theta_{i+1}\hskip
5.69046pt\forall i\in\\{1,2,\ldots,M-1\\}$. That is, the total minimal and
maximal waiting time that needs to be distributed in the sequence may only
increase between consecutive nodes. As such, note that the total minimal
waiting time $\Delta_{M}$, i.e. at the destination depot, represents a waiting
time amount that cannot be avoided in any feasible solution. Finally, the
objective of the problem reduces to optimally distribute $\Delta_{M}$ among
all nodes $\\{1,\ldots,M\\}$ in consideration of the total load $L_{i}$ at
each node in the sequence, which impacts the total user excess ride time.

##  3 Scheduling Procedure

In order to solve (LP2), we propose the procedure reported in the pseudo-code
from Algorithm (1) and explained next. The algorithm proceeds in the sense of
the sequence and checks that, for each encountered node
$i\in\\{1,\ldots,\bar{M}\\}$, a minimal total waiting time $\Delta_{i}$ has
been assigned up to node $i$. If the algorithm detects a total waiting time
shortage at node $i$, i.e. $\sum\limits_{k=1}^{i}w_{k}<\Delta_{i}$, the total
waiting time at $i$ and its preceding nodes needs to be increased. Given that
the objective function depends on the total vehicle load $L_{i}$, the
algorithm starts by considering adding waiting time to nodes $j\leq i$
featuring the lowest minimal total load up to $i$, i.e.
$j=\operatorname*{argmin}_{k\in\\{1,\ldots,i\\}}L_{k}$. Note that, if multiple
nodes featuring an equivalent minimal total load exist, the first node can be
selected without loss of generality. For node $j$, the total waiting time can
be feasibly increased by a maximum amount $\delta w_{j}$ defined by
constraints (15) and (16). That is, while deciding upon an increment in
waiting time at node $j$, one needs to check that excess-ride time constraints
are not violated for requests whose pickups precede $j$ and whose dropoffs
follow $j$. Furthermore, in order to guarantee time-window feasibility of the
whole sequence, one needs to check that an increment in waiting time at $j$
does not exceed the maximal waiting time that can be assigned to up to node
$j$, i.e. $\Theta_{j}-\sum\limits_{k=1}^{j}w_{k}$. Finally, waiting time at
node $j$ can be incremented by $\delta w_{j}$, which is computed as the
minimum between the amount defined by excess-ride time constraints, time-
window constraints, and the total waiting time shortage defined by
$\Delta_{i}-\sum\limits_{k=1}^{i}w_{k}$. After the update of $w_{j}$, if node
$j$ has reached its maximum waiting time limit by updating $\Delta_{i}$, that
is $\delta w_{j}<\Delta_{i}-\sum\limits_{k=1}^{i}w_{k}$, node $j$ is removed
from the list $\Omega$ of potential nodes whose waiting time may be further
increased. If $\sum\limits_{k=1}^{i}w_{k}<\Delta_{i}$, i.e. there is still a
total waiting time shortage at $i$, the total waiting time is increased at the
next node $\bar{j}$ up to $i$ featuring the second lowest total vehicle load.
This iterative process terminates as soon as
$\sum\limits_{k=1}^{i}w_{k}\geq\Delta_{i}$, that is when sufficient waiting
time has been assigned to $i$ and all of its preceding nodes. In this case,
the algorithm moves inspecting $i+1$ and up to the end of the sequence. If at
the end of the whole process, $\Delta_{\bar{M}}$ has been feasibly assigned,
the algorithm terminates with a feasible solution. Section 3.1 shows that if a
feasible solution is not obtained, this may lead to an incorrect infeasibility
declaration due to maximum ride time violations. On these solutions, it is
possible to recover feasibility through the recourse heurisitc presented in
Section 3.2, which is applied at step 17. in Algorithm (1). Note that the
procedure between line 1. and 15. of Algorithm (1) results in a worst-time
complexity of $O(\bar{M}^{2})$, since in the worst case, the step reported in
line 6. may be executed $\bar{M}$ times and the procedure in line 8. contains
at most $\bar{M}$ components. However, the application of the recourse
heuristic leads to a worst-time complexity of $O(n\times\bar{M}^{2})$, since,
Algorithm (1) may be restarted as many times as the number of requests $n$.
Finally, note that Algorithm (1) can either terminate with a feasible
solution, a correct infeasibility declaration, a suboptimal solution, or with
an incorrect infeasible solution, on which feasibility can be heuristically
recovered.

Input: vehicle route sequence ($\bar{I}=\\{1,\ldots,\bar{M}\\}$), pickups
$P_{i}$, dropoffs $D_{i}$, earliest start times $ET_{i}$, latest start times
$LT_{i}$, maximum ride times $u_{P_{i}}$, service durations $s_{i}$, travel
times $t_{i,j}$

Output: Waiting times $w_{i}$ with $i\in\bar{I}$, feasibility $check$

1 initialize $w_{i}.=0\hskip 5.69046pt\forall i\in\\{1,\ldots,\bar{M}\\}$;

2 initialize $\Omega=\emptyset$ ;

3 initialize $start$ $node=1$;

4 initialize $check=true$;

5 while  _$check=true$_ do

6 for  _$i\rightarrow$ $start$ $node$:$\bar{M}$_ do

7 Update: $\Omega=\Omega\cup\\{i\\}$ ;

8 while  _$\sum\limits_{k=1}^{i}w_{k} <\Delta_{i}$_ do

9 Set: $j=\operatorname*{argmin}_{k\in\Omega}L_{k}$ ;

10 Compute: $\delta w_{j}=\min\\{\min_{k\in\\{P|k\leq j\hskip
2.84544pt\&\hskip 2.84544ptn+k\geq
j\\}}u_{k}-\sum\limits_{l=k}^{(n+k)-1}t_{l,l+1}-\sum\limits_{l=k+1}^{(n+k)-1}d_{l}-\sum\limits_{l=k+1}^{n+k}w_{l};\hskip
2.84544pt\Theta_{j}-\sum\limits_{k=1}^{j}w_{k};\hskip
2.84544pt\Delta_{i}-\sum\limits_{k=1}^{i}w_{k}\\}$;

11 Set: $w_{j}=w_{j}+\delta w_{j}$;

12 if  _$\delta w_{j} <\Delta_{i}-\sum\limits_{k=1}^{i}w_{k}$_ then

13 Update: $\Omega=\Omega\setminus\\{j\\}$;

14 if  _$\sum\limits_{k=1}^{i}w_{k}\geq\Delta_{i}$_ then

15 break;

16 if  _$\sum\limits_{k=1}^{i}w_{k} <\Delta_{i}$ $\&$ $\Omega=\emptyset$_ then

17 Employ: $Recourse$ $heuristic$ (Algorithm 2);

18 if  _Recourse heuristic is not successful_ then

19 $check=false$;

20 break;

21 else

22 $start$ $node=j+1\leq i$;

23 Update waiting times;

24 Restart algorithm from line 6.

25

26

27

28

Algorithm 1 Ride time-oriented scheduling algorithm

###  3.1 Incorrect infeasibility declarations

There may be cases in which, at the end of Algorithm (1), the total waiting
time shortage $\Delta_{\bar{M}}$ cannot be feasibly assigned. In particular,
it is possible that the waiting times at all nodes preceding $i$ have been
updated, i.e., $\Omega=\emptyset$, but there is still a shortage of waiting
time at node $i$, i.e., $\sum\limits_{k=1}^{i}w_{k}<\Delta_{i}$. In this case,
the Algorithm (1) prematurely terminates and the sequence is deemed
infeasible. However, note that, due to the myopic nature of the procedure,
this may result in an incorrect infeasibility declaration. In fact, the
procedure is designed to assign waiting times to nodes $j\leq i$ based on the
waiting times shortage $\Delta_{i}$ and without considering the waiting times
shortages at subsequent nodes $\\{i+1,\ldots,\bar{M}\\}$. To ensure
feasibility at subsequent nodes after detecting a waiting times shortage
$\Delta_{i}$, it may be necessary to apply waiting times to nodes $j\leq i$
that:  1. are not the first node among nodes featuring the lowest total load;
and  2. do not feature the lowest total load  . Failing to apply waiting times
at the right nodes without knowledge of future waiting times shortages may
result in situations in which the nodes in $\Omega$ cannot be further pushed
forward in time without violating the maximum ride time constraints of nodes
in $\Omega$ and, consequently, an incorrect infeasibility declaration.

Figure 1: Example of a route leading to an incorrect infeasibility declaration

This drawback is illustrated in the routing sequence in Figure 1 and explained
next. Suppose that, at iteration ten, Algorithm (1) detects a waiting time
shortage $\Delta_{P_{10}}>0$ and that all of this waiting time shortage is
applied at pickup node $P_{10}$, given that it features the lowest total load
among all of its preceding nodes. As a consequence of increasing the waiting
times at node $P_{10}$, suppose that the service start time at node $D_{6}$
reaches the latest service start time $dep_{D_{6}}$ and that the ride time of
node $P_{7}$, with dropoff location $D_{7}$, reaches its maximum. The
algorithm proceeds inspecting the sequence and a new waiting times shortage is
detected at node $P_{12}$, i.e., $\Delta_{P_{12}}>0$. However, it is not
possible to increase waiting times at nodes preceding $P_{12}$, given the time
window constraints at node $D_{6}$, and it is not possible to increase the
waiting times at node $\Delta_{P_{12}}$, given the maximum ride time
constraints at node $D_{7}$. In this case, the scheduling algorithm
prematurely terminates and returns an infeasibility declaration for the given
sequence. However, this is an incorrect infeasibility declaration given that a
feasible solution can be constructed by applying the waiting time shortage
$\Delta_{P_{10}}$ at node $P_{7}$ instead of node $P_{10}$, although the total
load at node $P_{7}$ is higher than the total load at node $P_{10}$. This
reduces the ride time of node $P_{7}$, with dropoff location $D_{7}$ following
node $P_{12}$. Consequently, the waiting times shortage $\Delta_{P_{12}}$ can
be applied at node $P_{12}$, without violating the maximum ride time
constraints of node $P_{7}$ and a feasible solution is returned. To prevent
incorrect infeasibility declarations, we propose a recourse heuristic, whose
aim is to revisit previously-made waiting time decisions and decrease the
chances of obtaining incorrect infeasibility declarations. The details of the
recourse heuristic are provided in Algorithm 2 and are explained next.

###  3.2 Recourse heuristic to reduce incorrect infeasibility declarations

Input: vehicle route sequence ($\bar{I}=\\{1,\ldots,\bar{M}\\}$), pickups
$P_{i}$, dropoffs $D_{i}$, earliest start times $ET_{i}$, latest start times
$LT_{i}$, maximum ride times $u_{P_{i}}$, service durations $s_{i}$, travel
times $t_{i,j}$, waiting times $w_{i}$, remaining waiting time shortening
$\Delta_{i}$

Output: start node $start$ $node$, waiting times $w_{i}$ with $i\in\bar{I}$,
feasibility $check$

1 initialize $start$ $node=1$;

2 initialize $check=false$;

3 find all nodes $j_{l}\leq i$, $l\in\\{1,\ldots,\tilde{M}\\}$ that have
reached maximum ride time constraints;

4 for  _$l\rightarrow$ 1:$\tilde{M}$_ do

5 Set: $\tilde{w}_{i}=w_{i}$, $\tilde{w}_{i}=0$ $\forall
i\in\\{j_{l+1},\ldots,i\\}$;

6 Recompute: $LT_{i}$ ;

7 Compute: $\delta\tilde{w}_{j_{l}}$ as in step 10. of Algorithm 1;

8 if  _$\delta w_{j_{l}} >0$_ then

9 Update: $\tilde{w}_{j_{l}}=\tilde{w}_{j_{l}}+\delta w_{j}$;

10 Update: $start$ $node=j_{l}$;

11 Update: $check=true$;

12 Set: $w_{i}=\tilde{w}_{i}$;

13 break;

14

15

Algorithm 2 Recourse algorithm

Suppose that the scheduling algorithm has detected a waiting times shortage
$\Delta_{i}$ at node $i$ and that, after inspecting all nodes $j\leq i$,
$\Delta_{i}>0$ and $\Omega=\emptyset$. In this case, it may be necessary to
modify waiting time decisions that were taken at steps preceding $i$ through a
heuristic procedure, e.g., Algorithm 2. In particular, there may exists nodes
that reached their maximum ride time as a consequence of waiting time
decisions at previous nodes featuring the lowest total loads. Nodes $j\leq i$
that reached their maximum ride time can be detected by employing the first
term in step 10. of Algorithm 1. Suppose that $\tilde{M}$ nodes
$j_{1}<j_{2}<\ldots<j_{i}$ have reached their maximum ride time at iteration
$i$. This means that, in order to recover a feasible route, the sum of the
waiting time at these nodes need to be shifted by a total of $\Delta_{i}$.
Note that postponing the service start time at $j_{l}$,
$l\in\\{1,\ldots,\tilde{M}\\}$, automatically postpones the service start
times at any successive nodes, including nodes $j_{2},\ldots,j_{i}$.
Furthermore, it may modify waiting time decisions at nodes following $j_{l}$.
As such, the recourse heuristic iteratively explores possibilities to postpone
service start times at nodes $j_{l}$, $l\in\\{1,\ldots,\tilde{M}\\}$, by
employing the conditions defined by constraints (15) and (16) and employed in
step 10. of Algorithm (1). Note that the proposed recourse algorithm is a
heuristic, given that the waiting time shortage could be applied at nodes
$j_{l}$ as well as nodes preceding $j_{l}$. If the waiting times at node
$j_{l}$ can be postponed by a maximum amount $\delta w_{j_{l}}>0$, the waiting
time at $j_{l}$ is updated, the waiting times at all nodes following $j_{l}$
are re-initialized, and Algorithm (1) is re-started from $j_{l+1}$. Otherwise,
if $\delta w_{j_{l}}=0$ $\forall j_{l}$, $l\in\\{1,\ldots,\tilde{M}\\}$, then
the solution is deemed infeasible and Algorithm (1) is prematurely terminated.

##  4 Battery Management Problem

In the case of electric and autonomous vehicles, i.e., an e-ADARP, it is
necessary to show that the retrieved excess-time optimal schedules are also
battery-feasible. Indeed, Algorithm (1) disregards battery considerations
which are instead part of e-ADARPs. Battery-feasibility aspects can be
implemented by integrating battery-related decision variables and constraints
into (LP1), as presented in Section 2.2 in Bongiovanni et al. (2019), and
summarized next.

Consider the predetermined route sequence $\mathcal{I}$ of $M$ nodes. As
described in Section 2, this route originates at an origin depot, terminates
at a destination depot, visits a total of $n$ requests, and may pass through
$N$ charging stations $s\in\mathcal{S}\subset\mathcal{I}$. The latter are
necessary to refill the battery level $B_{i}$ of the vehicle after spending
battery inventory at rate $\beta_{i,i+1}$, for $i\in\\{1,\ldots,M-1\\}$. The
vehicle can only access charging stations $s\in\mathcal{S}$ when no requests
are onboard and is allowed recharge for a variable duration $E_{s}$ at rate
$\alpha_{s}$. Furthermore, it departs from the origin depot with a pre-defined
vehicle battery inventory $B_{init}$ and is required to reach the destination
depot with a minimal vehicle battery inventory $B_{end}$. The latter is
defined as a proportion of the total vehicle battery capacity $Q$, by means of
a minimal battery level ratio $r$. Under these settings, the integrated
scheduling and battery management problem is represented as (LP1),
supplemented with the following constraints:

$B_{i}=B_{init}\hskip 14.22636pti=1$ (17) $B_{i+1}\leq
B_{i}-\beta_{i,i+1}\hskip 14.22636pt\forall
i\in\\{1,\ldots,M-1\\}\setminus\mathcal{S},i\neq j$ (18) $B_{i+1}\geq
B_{i}-\beta_{i,i+1}\hskip 14.22636pt\forall
i\in\\{1,\ldots,M-1\\}\setminus\mathcal{S}$ (19) $B_{s+1}\leq
B_{s}+\alpha_{s}E_{s}-\beta_{s,s+1}\hskip 14.22636pts\in\mathcal{S}$ (20)
$B_{s+1}\geq B_{s}+\alpha_{s}E_{s}-\beta_{s,s+1}\hskip
14.22636pts\in\mathcal{S}$ (21) $Q\geq B_{s}+\alpha_{s}E_{s}\hskip
14.22636pt\forall s\in\mathcal{S}$ (22) $B_{i}\geq rQ\hskip 14.22636pti=M$
(23) $E_{s}\leq T_{s+1}-t_{s,s+1}-T_{s}\hskip 14.22636pt\forall
s\in\mathcal{S}$ (24) $E_{s}\geq T_{s+1}-t_{s,s+1}-T_{s}\hskip
14.22636pt\forall s\in\mathcal{S}$ (25) $B_{i}\geq 0\hskip 14.22636pt\forall
i\in\mathcal{I}$ (26) $E_{s}\geq 0\hskip 14.22636pt\forall s\in\mathcal{S}$
(27)

###  4.1 Battery management heuristic

Input: vehicle route sequence ($I=\\{1,\ldots,\bar{M}\\}$), Waiting times
$w_{i}$ ($i\in\mathcal{I}$), charging facilities $\\{s_{1},\ldots,s_{N}\\}$,
charging rates $\alpha_{s}$, discharging rate $\beta$, travel times
$t_{i,i+1}$, earliest start times $ET_{i}$, latest start times $LT_{i}$, State
of charge $B_{i}$

Output: Charging times $E_{s}$ with $s\in\\{s_{1},\ldots,s_{N}\\}$, Boolean
battery feasibility check

1 initialize $check=true$;

2 initialize $B_{1}=B_{0}$ ;

3 while  _$check=true$_ do

4 for  _$i\rightarrow$ 2:$\bar{M}$_ do

5 Compute: $B_{i}=B_{i-1}-\beta\times t_{i,j}$;

6 if  _$B_{i} <0$_ then

7 the sub-sequence is infeasible $\rightarrow$ $check=false$;

8 if  _$i\in\mathcal{S}$_ then

9 Set: $E_{i}=\min\\{LT_{i+1}-ET_{i};(Q-B_{i})/\alpha_{i}\\}$;

10 Set: $B_{i}=B_{i}+E_{i}$;

11 Update: $w_{i}$ $\forall i\in\\{i,\ldots,\bar{M}\\}$;

12

13

Algorithm 3 Battery management heuristic

The battery management problem, defined by (LP1) supplemented with constraints
(17)-(27), is solved through the battery management heuristic in Algorithm 3,
which builds on the assumption that battery levels can be seen as an inventory
which can only decrease with traveling. Then, for feasibility purposes, it is
always better to recharge as much as possible, as early as possible. If the
schedule that maximizes battery recharging does not satisfy the imposed
battery management constraints, no other recharging plan may be feasible,
i.e., the given sequence and excess-time optimal schedule is declared
infeasible. This is due to the fact that the scheduling algorithm presented in
Algorithm 1 is designed to minimize the completion time and, consequently, to
provide the shortest schedules and the longest charging opportunities.
Consequently, if battery feasible solutions do exist, at least one of them
minimizes the total user excess ride time. Note that the proposed recharging
procedure in Algorithm 3 is a heuristic since it cannot be formally proven
optimal (e.g. maximizing the charging time at station $i$ may decrease
opportunities to recharge more at following charging stations).

The battery management heuristic in Algorithm 3 considers the route schedule
computed by employing Algorithm 1 and sequentially computes the battery
inventory between successive nodes in consideration of the initial battery
level $B_{1}$, the battery discharge rate $\beta$, and the total travel time
up to $i$. Note that battery discharge can be equally computed by energy
consumption models (Goeke and Schneider 2015, Pelletier et al. 2017). During
this iterative process, when a charging facility is encountered, its maximal
recharging time is bound by:  (i) the difference between the service start
time at the current node and the latest service start time at the following
node, and  (ii) the time needed to fully recharge.  To ensure feasibility, the
recharging time at the station needs to be set to the minimum of the two.
After the charging time is calculated, the station’s battery level and the
waiting times of the station and subsequent nodes are updated. The procedure
prematurely terminates only if a node $i$ features a negative battery
inventory, after which the route is declared battery-infeasible.

##  5 Numerical Results

Numerical experiments are performed on the DARP instances presented in Cordeau
and Laporte (2003) and on the e-ADARP instances presented in Bongiovanni et
al. (2019). Specifically, we extract routing solutions by employing the
adaptive large neighborhood search described in Ropke and Pisinger (2006),
with 1,000 iterations. For each problem instance, the initial solution is
constructed from the best known solution, if available, or by employing a
construction heuristic in which a random subset of customers are assigned to
the vehicles, and served in a taxi mode (i.e., pickup-dropoffs). At every
iteration of the large neighborhood search, we solve the scheduling problem
through a linear program and compare its results to the route evaluation
procedures by Cordeau and Laporte (2003), Parragh et al. (2009), and
Molenbruch et al. (2017b), as well as this paper. This results in a thorough
comparison of the scheduling algorithms on 21,844,304 feasible DARP solutions
and 2,370,243 feasible e-ADARP solutions. The numerical experiments are
implemented in Julia v1.8.2 and run on 2 x AMD Rome 7532 @ 2.40 GHz 256M cache
L3 CPU clusters. Each instance is run on five of such CPUs with 186 Gb of RAM.
The LP is implemented in the JuMP modeling language (Dunning et al. 2017)
v1.3.1 and solved with Gurobi v 0.11.3.

darpexcel/darp/Table_logs.csv

Table 1: Scheduling algorithms on DARP instances: number of incorrect
infeasible declarations, number of deviating solutions, and average relative
deviation.

| Algorithm (1) | Cordeau and Laporte (2003) | Parragh et al. (2009) | Molenbruch et al. (2017b)
---|---|---|---|---
Name | #Routes | Size range | #Inf. | #Dev. | Avg. dev. % | #Inf. | #Dev. | Avg. dev. % | #Inf. | #Dev. | Avg. dev. % | #Inf. | #Dev. |

Table 1 shows a comparison between the scheduling procedures on DARP
instances. The first column indicates the instance name, following the
convention employed in Cordeau and Laporte (2003). These are instances that
consider three to 13 vehicles and 24 to 144 requests. For further information
on the generation of these DARP instances, the reader is referred to Cordeau
and Laporte (2003). The second column indicates the total number of evaluated
feasible routes, and the third column the range of their size, i.e., the
number of nodes in the routes. The fourth to sixt column show the total number
of incorrect infeasible declarations, the total number of deviating solutions,
and their absolute average percentage deviation from the optimal solution, by
employing Algorithm (1). The following columns show the same results for the
8-step scheduling algorithms by Cordeau and Laporte (2003), Parragh et al.
(2009), and Molenbruch et al. (2017b). As it can be noted, Algorithm (1) does
not return any incorrect infeasibility declaration. However, in some very rare
cases (i.e., in only 27 occurrences over more than 21.5 million cases), it
does return suboptimal solutions, namely for instances pr06, pr09, and,
mostly, pr16. For these instances, the returned suboptimal solutions deviate
by less than 2.5%, on absolute average terms. This consists of a very small
proportion of suboptimal solutions, compared to the results obtained by
employing the scheduling algorithms by Cordeau and Laporte (2003), Parragh et
al. (2009), and Molenbruch et al. (2017b). Consistently with reported results
from the literature, the approach by Cordeau and Laporte (2003) has the
tendency to minimize the total number of incorrect infeasibility declarations
at the cost of a higher number of suboptimal solutions and their average
deviations. Namely, the approach returns about 27% suboptimal solutions, with
deviations between about 8% and 27%. The approach by Parragh et al. (2009),
instead, has the tendency to minimize the total number of suboptimal solutions
and their average deviation, at the cost of a higher number of incorrect
infeasibility declarations. Namely, the approach returns up to 0.007%
incorrect infeasibility declarations but reduces the number of suboptimal
solutions to about 0.5%, with deviations between about 2.5% and 10%. The
procedure by Molenbruch et al. (2017b) produces similar results with respect
to the procedure by Parragh et al. (2009), most specifically in terms of the
number of incorrect infeasibility declarations. However, the the number of
suboptimal solutions to 0.23%, with deviations between about 2% and 9.5%. It
is worth noting that, in our numerical experiments, all incorrect
infeasibility declarations returned by the scheduling algorithms by Parragh et
al. (2009) and Molenbruch et al. (2017b) are due to violations of maximum ride
time constraints. In addition to producing solutions of higher quality with
respect to state-of-the-art scheduling algorithms, Algorithm (1) is
computationally efficient, as shown in Table 2. It is about 60% faster than a
linear program and comparably efficient with respect to the scheduling
algorithms by Cordeau and Laporte (2003), Parragh et al. (2009), and
Molenbruch et al. (2017b), with a slight computational disadvantage for small-
scale instances, e.g. pr01, and advantage for large-scale instances, e.g.,
instances pr18, pr19, and pr20.

Table 2: Scheduling algorihtms on DARP instances: CPU times [ms]

| Linear Program | Algorithm (1) | Cordeau and Laporte (2003) | Parragh et al. (2009) | Molenbruch et al. (2017b)
---|---|---|---|---|---
Name | Avg. CPU [ms] | Avg. CPU [ms] | Avg. CPU [ms] | Avg. CPU [ms] |

uberexcel/uber/Table_logs.csv

Table 3: Scheduling algorithms on E-ADARP instances: number of incorrect
infeasible declarations, number of deviating solutions, and average relative
deviation.

| Algorithm (1) | Cordeau and Laporte (2003) | Parragh et al. (2009) | Molenbruch et al. (2017b)
---|---|---|---|---
Name | #Routes | Size range | #Inf. | #Dev. | #Inf. | #Dev. | Avg. dev. % | #Inf. | #Dev. | Avg. dev. % | #Inf. | #Dev. |

Table 3 shows a comparison between the investigated scheduling procedures on
e-ADARP instances. The first column indicates the instance name, following the
convention employed in Bongiovanni et al. (2019), i.e., $<$u$>$$<$number of
vehicles$>$-$<$number of customers$>$-$<$minimum battery inventory ratio at
the destination depot$>$,“u" is used to refer to the instances adapted from
real data from Uber Technologies Inc. Furthermore, the reader is reminded that
the minimum battery inventory ratio is used to compute the minimal battery
levels that all vehicles need to have at the destination depot, i.e. a minimal
battery ratio of 0.7 means vehicles need to have at least 70% of their nominal
battery capacity at the destination depot. The following columns adopt the
same convention used in Table 1. As it can be noted, in this case Algorithm
(1) always returns optimal scheduling solutions, which include charging
decisions. Differently from the DARP results shown in Table 1, the approach of
Cordeau and Laporte (2003) return some incorrect infeasibility declarations,
although this remains limited to about 0.05%. The number of suboptimal
solutions, however, rise up to about 34% and so their absolute average
deviations from the optimal solution, which range between about 24% and more
than 100%. The approach of Parragh et al. (2009) also shows an increase in the
total number of incorrect infeasibility declarations with respect to the DARP
results shown in Table 1. Namely, the total number of infeasibility
declarations rise to at most about 10%, however, the number of suboptimal
solutions decrease to about 0.006%, with deviations which are contained
between about 0.5% and 7%. Finally, the approach of Molenbruch et al. (2017b)
shows a net decrease both in terms of the total number of incorrect
infeasibility declarations and suboptimal solutions, with a total of eight
occurrences over more than 2 million cases, with respect to the DARP results
shown in Table 1.

Table 4: Scheduling algorithms on E-ADARP instances: infeasibility reasons

| Cordeau and Laporte (2003) | Parragh et al. (2009) | Molenbruch et al. (2017b)
---|---|---|---
Name | #Inf. TW | #Inf. RT | #Inf. BATT | #Inf. TW | #Inf. RT | #Inf. BATT | #Inf. TW | #Inf. RT |

Table 5: Scheduling algorihtms on E-ADARP instances: CPU times [ms]

| Linear Program | Algorithm (1) | Cordeau and Laporte (2003) | Parragh et al. (2009) | Molenbruch et al. (2017b)
---|---|---|---|---|---
Name | Avg. CPU [ms] | Avg. CPU [ms] | Avg. CPU [ms] | Avg. CPU [ms] |

As shown in Table 4, in the case of an e-ADARP, the procedure by Cordeau and
Laporte (2003) mostly produce solutions that violate ride time constraints,
whereas the procedure by Parragh et al. (2009) mostly violate time window and
battery constraints. This last procedure is in fact designed to minimize
completion time, which, in turn, may increase the chances of violating battery
management constraints. As for the DARP results shown in Table 1, the
procedure by Molenbruch et al. (2017b) may violate ride time constraints.
Finally, Table 5 shows the average CPU times, in milliseconds, obtained by
running the linear program, Algorithm (1), and the scheduling procedures by
Cordeau and Laporte (2003), Parragh et al. (2009), and Molenbruch et al.
(2017b) on the e-ADARP. As it can be noted, also in this case, Algorithm (1)
is about 60% faster with respect to a linear program, on average, and up to
about 80-85% faster, e.g. for instance u5-40-0.7 and instances u4-16. Savings
in terms of computing time might be even more significant when considering
larger problem instances or when several static problems are solved in real
time, e.g. as in the dynamic e-ADARP presented in Bongiovanni et al. (2022).

##  6 Summary

This work proposed an excess-ride-time procedure for scheduling dial-a-ride
instances. The procedure is shown to produce high-quality solutions, which are
only very rarely suboptimal, in at least half the time of a linear program and
in comparable time with respect to state-of-the-art scheduling algorithms. The
proposed procedure can be potentially employed to efficiently solve scheduling
problems from static and dynamic metaheuristic appraches. For the e-ADARP, we
further propose a battery heuristic which can be used when the vehicle routes
include one or more visits to charging facilities. The heuristic is needed to
provide battery-feasible charging plans for the vehicle schedules. The battery
heuristic builds on the assumption that charging as much as possible as early
as possible is the best strategy for battery-feasibility.

Computational experiments are carried on a plethora of static DARP and e-ADARP
instances from the literature, which are extracted from an adaptive large
neighborhood search with 1,000 iterations. Experiments show that the route
evaluation procedure is computationally more efficient than solving a linear
program, while returning higher-quality solutions with respect to popular
scheduling heuristics from the literature. Furthermore, results show that the
proposed scheduling procedure does not produce incorrect infeasibility
declarations and produces suboptimal solutions in very rare cases (i.e., in
about 0.0001 % of times, which deviate up to 2.5% from optimal solutions, on
average).

## Acknowledments

This research was enabled in part by support provided by Calcul Québec
(www.calculquebec.ca/en/) and Compute Canada (www.computecanada.ca).

## References

  * Bongiovanni et al. (2022) Bongiovanni, C., Kaspi, M., Cordeau, J.F., Geroliminis, N., 2022\.  A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations.  Transportation Research Part E: Logistics and Transportation Review 165, 102835.
  * Bongiovanni et al. (2019) Bongiovanni, C., Kaspi, M., Geroliminis, N., 2019.  The electric autonomous dial-a-ride problem.  Transportation Research Part B: Methodological 122, 436–456.
  * Cordeau and Laporte (2003) Cordeau, J.F., Laporte, G., 2003\.  A tabu search heuristic for the static multi-vehicle dial-a-ride problem.  Transportation Research Part B: Methodological 37(6), 579–594.
  * Cordeau and Laporte (2007) Cordeau, J.F., Laporte, G., 2007\.  The dial-a-ride probelm: models and algorithms.  Annals of Operations Research 153, 29–46.
  * Dunning et al. (2017) Dunning, I., Huchette, J., Lubin, M., 2017.  Jump: A modeling language for mathematical optimization.  SIAM Review 59, 295–320.
  * Goeke and Schneider (2015) Goeke, D., Schneider, M., 2015\.  Routing a mixed fleet of electric and conventional vehicles.  European Journal of Operational Research 245, 81–99.
  * Gschwind and Drexl (2019) Gschwind, T., Drexl, M., 2019\.  Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem.  Transportation Science 53, 480–491.
  * Molenbruch et al. (2017a) Molenbruch, Y., Braekers, K., Caris, A., 2017a.  Typology and literature review for dial-a-ride problems.  Annals of Operations Research 259 (1-2), 295–325.
  * Molenbruch et al. (2017b) Molenbruch, Y., Braekers, K., Caris, A., Berghe, G.V., 2017b.  Multi-directional local search for a bi-objective dial-a-ride problem in patient transportation.  Computers & Operations Research 77, 58–71.
  * Parragh et al. (2009) Parragh, S.N., Doerner, K.F., Hartl, R.F., Gandibleux, X., 2009\.  A heuristic two-phase solution approach for the multi-objective dial-a-ride problem.  Networks: An International Journal 54, 227–242.
  * Pelletier et al. (2017) Pelletier, S., Jabali, O., Laporte, G., Veneroni, M., 2017\.  Battery degradation and behavior for electric vehicles: Review and numerical analyses of several models.  Transportation Research Part B: Methodological 103, 158–187.
  * Ropke and Pisinger (2006) Ropke, S., Pisinger, D., 2006\.  An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows.  Transportation science 40, 455–472.
  * Savelsbergh (1992) Savelsbergh, M.W., 1992.  The vehicle routing problem with time windows: Minimizing route duration.  ORSA Journal on Computing 4, 146–154.
  * Vidal et al. (2015) Vidal, T., Crainic, T.G., Gendreau, M., Prins, C., 2015\.  Timing problems and algorithms: Time decisions for sequences of activities.  Networks 65, 102–128.
  * Yue et al. (2023) Yue, S., Dupin, Nicolas, Puchinger, J., 2023\.  A deterministic annealing local search for the electric autonomous dial-a-ride problem.  European Journal of Operational Research.
  * Yue et al. (2022) Yue, S., Dupin, Nicolas, Parragh, S., Puchinger, J., 2022\.  A Column Generation Approach for the Electric Autonomous Dial-a-Ride Problem.  arXiv preprint arXiv:2206.13496.