# Kinship Verification from rPPG using 1DCNN Attention networks

###### Abstract

Facial kinship verification aims at automatically determining whether two
subjects have a kinship relation. It has been widely studied from different
modalities, such as faces, voices, gait, and smiling expressions. However, the
potential of bio-signals, such as remote Photoplethysmography (rPPG) extracted
from facial videos, remains largely unexplored in the kinship verification
problem. In this paper, we investigate for the first time the usage of the
rPPG signal for kinship verification. Specifically, we proposed a one-
dimensional Convolutional Neural Network (1DCNN) with a 1DCNN-Attention module
and contrastive loss to learn the kinship similarity from rPPGs. The network
takes multiple rPPG signals extracted from various facial Regions of Interest
(ROIs) as inputs. Additionally, the 1DCNN attention module is designed to
learn and capture the discriminative kin features from feature embeddings.
Finally, the proposed method is evaluated on the UvANEMO Smile Database from
different kin relations, showing the usefulness of rPPG signals in verifying
kinship.

Index Terms—  Kinship verification, Remote Photoplethysmography, 1DCNN,
Channel attention, Biosignals

##  1 Introduction

Facial Kinship Verification (FKV)[1] recognizes the human biometric
relationships through facial features. Compared with the Face Verification
problem, FKV is more challenging due to small intraclass similarity and large
interclass variance[1]. It has potential applications in genetic and
anthropological studies, social security, and locating missing children.
Recently, besides face modality, FKV has been widely explored using other
modalities such as smiling [2], voices [3], and gait [4].

Among various biometric traits, heart activities have indicated genetic
predisposition as early as 1925 [5]. Since then, many studies [6, 7] have
shown that Electrocardiogram (ECG) analysis of twins presents more significant
intra-pair similarities than those of unrelated individuals.

In recent years, physiological signals such as ECG, Photoplethysmography
(PPG), remote PPG, and Phonocardiogram (PCG) have been widely used in
automatic biometric recognition, such as HeartID [8] and Heart Biometric [9].
However, the study of kinship verification using physiological signals remains
largely unexplored.

Remote Photoplethysmography (rPPG) estimates the blood flow from facial videos
by detecting subtle changes in skin color associated with the cardiac cycle.
This non-invasive technique, which captures unique physiological patterns, has
sparked curiosity about its potential applications beyond mere heart rate
estimation. Inspired by biometric studies, in this paper, we pose the
question: Can we verify kinship from remote Photoplethysmography? To answer
this question, we present a proposed pipeline as shown in Fig. 1.

Fig. 1: Facial kinship verification using remote photoplethysmography.

As the pioneering study in this area, we carefully designed our experiment
based on the clear, front-facing UvANEMO Smile Database [10] that was
collected under controlled indoor conditions. Three rPPG methods are employed
to measure the rPPG signals from facial videos. To perform a comparison
between rPPG signals from the subject pair, we proposed a 1DCNN-Attention
model. 1DCNN is a typical deep learning method for processing one-dimensional
sequence data [11]. To enhance the robustness of the network, we use multiple
rPPG signals as inputs for each subject, resulting in a multi-channel data
configuration at the input layer. Furthermore, the 1DCNN channel attention
module is applied to learn discriminative kin features. The network employs a
Siamese-like architecture for the training. Finally, the contrastive loss is
added to guide model training.

Our contributions can be summarized as follows:

  * •

We explore the remote photoplethysmography for kinship recognition and
formulate the problem for the first time.

  * •

We introduce an effective 1DCNN-Attention model to adaptively capture kin-
related features from rPPGs for kinship verification.

  * •

Through experiments on the UvANEMO Smile Database [10], we demonstrate the
feasibility of verifying kinship using rPPGs and establish the first benchmark
for this approach.

##  2 rPPG Measurement from Facial Videos

The general workflow for facial remote photoplethysmography (rPPG) measurement
is illustrated in Figure 2. This study primarily investigates kinship
correlations using rPPG as the foundational element. It is noteworthy that
current kinship datasets do not incorporate physiological signals measured via
direct contact. Consequently, we have integrated three non-machine learning-
based rPPG methods from existing literature [12] into our analysis: CHROM
[13], LGI (Local Group Invariance) [14], and POS (Plane-Orthogonal-to-Skin)
[15]. These conventional rPPG techniques capture variations in facial color
caused by heartbeats and blood circulation.

CHROM method [13] derives rPPG signals by leveraging chrominance-related data.
It creates two orthogonal chrominance signals from the original RGB data to
reduce the impact of specular reflection. This reduction is achieved through a
linear combination of color components based on a skin reflection model.

LGI [14] processes the initial signal and maps it into an invariant space to
enhance the robustness of rPPG, especially when dealing with challenges like
motion and varying lighting conditions.

POS [15] introduces the concept of the Plane-Orthogonal-to-Skin. This
technique projects the color space onto a plane that is orthogonal to skin
color and then combines the results to generate the rPPG signal.

For our implementation, we select 100 facial Regions of Interest (ROIs) to
generate the remote photoplethysmogram (PPG). Those rPPG signals serve as the
input to our network, consolidating data from various channels.

Fig. 2: The pipeline of the rPPG measurement. We apply three rPPG methods:
CHROM [13], LGI [14], POS [15].

##  3 Proposed network

Fig. 3: Architecture of the proposed 1D-CNN channel attention model for
kinship verification using facial rPPG. The model processes two rPPG inputs
sequentially through two 1D convolution layers, a channel attention module,
and three fully connected layers. ReLU serves as the activation function, and
the Dropout technique is applied at the end to the first two fully connected
layers. The network’s training is guided by the contrastive loss, which is
backpropagated for model updates.

In this section, we present our proposed 1DCNN-Attention model tailored for
kinship verification based on rPPGs. CNNs are designed to extract high-level
convolutional features directly from raw data. While 2DCNNs are conventionally
used for image processing, 1DCNNs are better suited for extracting spatial
features from one-dimensional signals, like time series. Importantly,
convolutional networks have demonstrated their proficiency in crafting
effective feature representations from raw one-dimensional data, offering
superior performance over deep multilayer perceptrons (MLP) without the need
for intricate preprocessing [11]. Incorporating an attention module allows for
the calculation of channel-wise self-adaptive weights, thereby facilitating
the learning of discriminative features. With the 1DCNN serving as the feature
extractor, the generated embeddings are subsequently projected through three
fully connected layers. To capture and accentuate kinship traits, a
contrastive loss is introduced at the network’s end, guiding the training
process. A visual representation of the entire architecture can be found in
Fig. 3.

###  3.1 1DCNN-Attention networks

The training set of the kinship verification is composed of multiple sample
pairs. We denote them with
$\mathcal{D}=\\{(\mathbf{P}_{i},\mathbf{C}_{i},l_{i}),|i=1,2,\dots N\\}$.
$\mathbf{P}_{i}$ and $\mathbf{C}_{i}\in\mathbb{R}^{C\times W}$ represent the
$i_{th}$ sample pair with rPPG generated by methods introduced in Section 2.
$C$ and $W$ represent the number of input channels and the dimension of the
rPPG signal. $l_{i}$ means the label to the $i_{th}$ sample pair, where $0$
represents that $\mathbf{P}_{i}$ and $\mathbf{C}_{i}$ are negative pairs
without a kinship relation and $1$ denotes positive pairs with a kin relation.

The sample pair is forwarded to the network with the same strategy. Let’s take
the $\mathbf{P}_{i}$ for an example. $\mathbf{P}_{i}$ first passed two
convolutional operations with 1-D kernels with the size of {5, 5}, stride {1,
1} without padding, and output channels are {32, 64}, respectively. The
convolutional computation block can be represented as:

$\left\\{\begin{matrix}\mathbf{y}=\mathbf{W}\otimes\mathbf{x}+b\\\
\mathbf{h}=ReLu(\mathbf{y})\par\end{matrix}\right.$ (1)

where $\otimes$ is the convolutional operation, $\mathbf{x}$ is the input to
the convolutional block, and $\mathbf{h}$ is the obtained feature embedding by
applying the ReLU activation function.

Channel Attention module Let
$\hat{\mathbf{P}_{i}}\in\mathbb{R}^{\hat{C}\times\hat{W}}$ be the feature
collected at the second convolutional block. $\hat{C}$ and $\hat{W}$
represents the number of channel and spatial dimension. To squeeze the global
information into channel-wise data distribution [16], a 1D global average
pooling is adopted. Following that, there are two FC layers with a reduction
ratio $r$. $r$ is set with 8. The channel-wise weight vector and output of the
attention module can be calculated by:

$\mathbf{w}_{p}=\sigma\left(FCs(g(\hat{\mathbf{{P}}_{i}}))\right),\mathbf{z}=\hat{\mathbf{{P}}_{i}}\mathbf{w}_{p}$
(2)

$\sigma(\cdot)$ is a Sigmoid function,
$g(\hat{\mathbf{{P}}_{i}})=1/\hat{W}\sum_{i=1}^{\hat{W}}\hat{\mathbf{{P}}_{ij}}$
is the 1D global average pooling. $FCs(\cdot)$ denotes two FC layers.
$\mathbf{z}$ has the same size as $\hat{\mathbf{P}_{i}}$. The final output can
be calculated by:

$\left\\{\begin{matrix}\mathbf{f}=FLATTEN(\mathbf{z})\\\
\mathbf{f}_{1}=DropOut(ReLu(FC1(\mathbf{f})))\\\
\mathbf{f}_{2}=DropOut(ReLu(FC2(\mathbf{f}_{1})))\\\
\mathbf{f}_{p}^{i}=FC3(\mathbf{f}_{2})\par\end{matrix}\right.$ (3)

$FLATTEN(\cdot)$ transforms the feature map $\mathbf{z}$ into a one-dimension
vector. The dropout rate is set at 0.1. After passing three FC layers, we can
collect the feature output as $\mathbf{f}_{p}^{i}$. Similarly, for the other
network input $\mathbf{C}_{i}$, the feature represented for it can be denoted
as $\mathbf{f}_{c}^{i}$.

###  3.2 Loss function

To force the face model to learn the robust rPPG feature representations for
kinship verification, we minimize the contrastive loss with the network
backpropagation:

$\begin{matrix}\mathcal{L_{rPPG}}=\frac{1}{N}\sum_{i=1}^{N}(l_{i}d_{i}^{2}+(1-l_{i})\max(\tau-
d_{i},0)^{2})\\\ s.t.\quad
d_{i}=\left\|\mathbf{f}_{p}^{i}-\mathbf{f}_{c}^{i}\right\|^{2}\end{matrix}$
(4)

$\tau$ is the hyperparameter, and $d_{i}$ denotes the Euclidean distance
between a sample pair.

##  4 Experiments

###  4.1 Implementation Details

Dataset and evaluation metric. The UvANEMO Smile Database is widely employed
for kinship verification studies [10]. It comprises front-facing videos of
spontaneous/posed smiles captured in a constrained indoor environment. These
videos have a resolution of 1920 × 1080 pixels and a frame rate of 50 FPS. The
database contains 1240 smile videos from 400 subjects spanning seven kin
relations 111Parent-Child kin relations: Father-Son (F-S), Father-Daughter
(F-D), Mother-Son (M-S), and Mother-Daughter (M-D); Sibling kin relations:
Brother-Brother (B-B), Sister-Sister (S-S), and Sister-Brother (S-B). Videos
range in duration from 1.1 to 14.3 seconds. To ensure a sufficient time window
for generating rPPG signals, we focus on videos lasting at least 2.5 seconds.
From this subset, we selected both negative and positive pairs meeting the
length criteria. The distribution of the seven kin relations within the data
is depicted in Fig. 4. In our experiments, we evaluate all seven relationship
types. The primary metric is the area under the receiver operating
characteristic (AUC), with the ROC curve visualizing model performance.

Training details. To validate the effectiveness of the proposed method, we
apply a leave-one-subject-out (LOSO) cross-validation scheme [2]. In this
scheme, one subject pair is reserved for testing, while the remaining data for
each kin relation is used for training. During the training of the proposed 1D
CNN, we allocate a portion of the training set as a validation set to monitor
the training process, using early stopping as needed. The network parameters
are optimized using the Adam optimizer with a learning rate of 1e-3 and a
mini-batch size of 30. The model is trained using the PyTorch framework on an
Nvidia Tesla V100 GPU (16 GB). The rPPG methods are implemented using
Face2PPG, a modified version of the pyVHR toolbox 2.0 [17,
18]222https://github.com/phuselab/pyVHR. We set the parameter $\tau$ to 1.

Table 1: Evaluation of our method on the UvANEMO Smile Database for seven kin relations using AUC (%). Different rPPG methods were employed. Bold numbers indicate the best results for each relation. Kin relations | Parent-Child | Siblings | Mean$\pm$Std.
---|---|---|---
F-S | F-D | M-S | M-D | B-B | S-B | S-S
1Dattention | LGI [14] | 71.27 | 63.57 | 65.07 | 64.87 | 55.89 | 55.50 | 54.41 | 61.51$\pm$6.34
CHROM [13] | 55.24 | 68.36 | 62.27 | 66.09 | 69.67 | 61.70 | 70.44 | 64.82$\pm$5.43
POS [15] | 70.43 | 68.61 | 68.94 | 70.42 | 61.65 | 72.43 | 72.47 | 69.28$\pm$3.69
Table 2: Ablation study of the proposed architecture on multichannel inputs and 1D channel attention. CA means the network channel attention. SingleChannel indicates that the input is one rPPG signal per facial video. The colored cells show the performance comparison of the proposed and ablated methods. Kin relations | Parent-Child | Siblings | Mean$\pm$Std.
---|---|---|---
F-S | F-D | M-S | M-D | B-B | S-B | S-S
SingleChannel | 66.35 | 66.43 | 66.14 | 71.18 | 53.00 | 66.70 | 71.43 | 65.89 $\pm$6.14
w/o. CA | 69.71 | 64.43 | 66.93 | 71.22 | 60.40 | 72.29 | 68.35 | 67.62$\pm$4.13
Proposed | 70.43 | 68.61 | 68.94 | 70.42 | 61.65 | 72.43 | 72.47 | 69.28$\pm$3.69
(Multi-channel) over (Single-channel) |  $\uparrow$4.08 |  $\uparrow$2.18 |  $\uparrow$2.80 |  $\downarrow$0.76 |  $\uparrow$8.65 |  $\uparrow$5.73 |  $\uparrow$1.04 |  $\uparrow$3.39
(w/ CA) over (w/o. CA) |  $\uparrow$0.72 |  $\uparrow$4.18 |  $\uparrow$2.01 |  $\downarrow$0.80 |  $\uparrow$1.25 |  $\uparrow$0.14 |  $\uparrow$4.12 |  $\uparrow$1.66

###  4.2 Results and analysis

Table 1 summarizes the results of the proposed 1DCNN model with the inputs of
rPPG signals generated by the LGI [14], CHROM [13], POS [15] methods,
respectively. On average, the model with the inputs of rPPG by POS [15] method
yields the best recognition performance, which shows the most discriminative
ability. The inputs by LGI [14] obtain the best performance on the F-S
relation, and CHROM [13] method can gain the best performance on the B-B
relation. These findings answer the research question posed in this paper,
showing the feasibility of kinship recognition using remote
photoplethysmography (rPPG).

Fig. 4: Data distribution within each kin relation in the subset of UvA-NEMO
Smile Database [10].

Additionally, we visually compare the performances of different rPPG methods
by displaying their respective ROC curves in Fig. 5(a). This visual
representation reinforces the notion that rPPG signals from the POS method
offer the highest level of discrimination.

###  4.3 Ablation Study

We conducted an ablation study based on our proposed model using rPPG inputs
generated by the POS method [15]. The results of this study are detailed in
Table 2, and the corresponding ROC curves are illustrated in Fig. 5(b). The
final two rows of the table provide a performance comparison for the two
ablation scenarios.

(a) rPPG methods

(b) Ablation study

Fig. 5: (a) The ROC curves comparison between different inputs by rPPG
methods. (b) The ROC curves comparison for the ablation study. Zoom in for
better visualization.

Comparison with Single Channel Input. Instead of utilizing a 100-channel rPPG
input, we also tested a single-channel rPPG derived from one facial video
using the holistic method from Face2PPG/pyVHR [17, 18]. All other model
components were kept consistent. As seen from the penultimate row in Table 2,
multi-channel rPPG inputs enhance the model’s robustness, yielding an average
performance improvement of 3.39%.

Effectiveness of Channel Attention. We evaluated the impact of the channel
attention module in our model, as presented in Table 2. “w/o. CA” denotes a
version of the network without the 1D CNN channel attention module. As
indicated in the last row of Table 2, incorporating the channel attention
module results in an average 1.66% AUC boost, underscoring its significance in
the model.

##  5 Conclusion

In this paper, we focus on addressing the kinship verification problem through
the rPPG signals extracted from facial videos. We propose a 1DCNN attention
network that leverages multiple rPPG as multi-channel inputs and incorporates
the 1D attention module to extract discriminative kin features. Our ablation
experiments demonstrate that the rPPG POS method yields the highest
discriminative ability, highlighting the effectiveness of our proposed model
components. The outcomes of this study may benefit the related multimodal
kinship and biometric studies. However, the robustness of our system with
noisy kinship data remains unexplored, subject to the robustness of rPPG
method. As part of our future work, we intend to delve into this aspect,
further enhancing the applicability of our approach.

## References

  * [1] Xiaoting Wu, Xiaoyi Feng, Xiaochun Cao, Xin Xu, Dewen Hu, Miguel Bordallo López, and Li Liu,  “Facial kinship verification: A comprehensive review and outlook,”  International Journal of Computer Vision, vol. 130, no. 6, pp. 1494–1525, 2022.
  * [2] Hamdi Dibeklioglu,  “Visual transformation aided contrastive learning for video-based kinship verification,”  in Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017, pp. 2459–2468.
  * [3] Xiaoting Wu, Xueyi Zhang, Xiaoyi Feng, Miguel Bordallo López, and Li Liu,  “Audio-visual kinship verification: a new dataset and a unified adaptive adversarial multimodal learning approach,”  IEEE Transactions on Cybernetics, 2022.
  * [4] Salah Eddine Bekhouche, Abdelhakim Chergui, Abdenour Hadid, and Yassine Ruichek,  “Kinship verification from gait,”  in 2020 IEEE International Conference on Image Processing (ICIP), 2020, pp. 2950–2954.
  * [5] Weitz W,  “Studien an eineiigen zwillingen,”  Z Klin Med, pp. 489–501, 1925.
  * [6] Mark W Russell, Ian Law, Phyliss Sholinsky, and Richard R Fabsitz,  “Heritability of ecg measurements in adult male twins,”  Journal of electrocardiology, vol. 30, pp. 64–68, 1998.
  * [7] Yogendra Narain Singh, Sanjay Kumar Singh, and Amit Kumar Ray,  “Bioelectrical signals as emerging biometrics: Issues and challenges,”  International Scholarly Research Notices, vol. 2012, 2012.
  * [8] S Zahra Fatemian, Foteini Agrafioti, and Dimitrios Hatzinakos,  “Heartid: Cardiac biometric recognition,”  in 2010 Fourth IEEE international conference on biometrics: theory, applications and systems (BTAS). IEEE, 2010, pp. 1–5.
  * [9] Aditya Singh Rathore, Zhengxiong Li, Weijin Zhu, Zhanpeng Jin, and Wenyao Xu,  “A survey on heart biometrics,”  ACM Computing Surveys (CSUR), vol. 53, no. 6, pp. 1–38, 2020.
  * [10] Hamdi Dibeklioğlu, Albert Ali Salah, and Theo Gevers,  “Are you really smiling at me? spontaneous versus posed enjoyment smiles,”  in European Conference on Computer Vision (ECCV). Springer, 2012, pp. 525–538.
  * [11] Zhiguang Wang, Weizhong Yan, and Tim Oates,  “Time series classification from scratch with deep neural networks: A strong baseline,”  in 2017 International joint conference on neural networks (IJCNN). IEEE, 2017, pp. 1578–1585.
  * [12] Nhi Nguyen, Le Nguyen, Constantino Álvarez Casado, Olli Silvén, and Miguel Bordallo López,  “Non-contact heart rate measurement from deteriorated videos,”  arXiv preprint arXiv:2304.14789, 2023.
  * [13] Gerard De Haan and Vincent Jeanne,  “Robust pulse rate from chrominance-based rppg,”  IEEE Transactions on Biomedical Engineering, vol. 60, no. 10, pp. 2878–2886, 2013.
  * [14] Christian S Pilz, Sebastian Zaunseder, Jarek Krajewski, and Vladimir Blazek,  “Local group invariance for heart rate estimation from face videos in the wild,”  in Proceedings of the IEEE conference on computer vision and pattern recognition workshops (CVPRW). IEEE, 2018, pp. 1254–1262.
  * [15] Wenjin Wang, Albertus C Den Brinker, Sander Stuijk, and Gerard De Haan,  “Algorithmic principles of remote ppg,”  IEEE Transactions on Biomedical Engineering, vol. 64, no. 7, pp. 1479–1491, 2016.
  * [16] Jie Hu, Li Shen, and Gang Sun,  “Squeeze-and-excitation networks,”  in Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), 2018, pp. 7132–7141.
  * [17] Giuseppe Boccignone, Donatello Conte, Vittorio Cuculo, Alessandro D’Amelio, Giuliano Grossi, Raffaella Lanzarotti, and Edoardo Mortara,  “pyvhr: a python framework for remote photoplethysmography,”  PeerJ Computer Science, vol. 8, pp. e929, 2022.
  * [18] Constantino Alvarez Casado and Miguel Bordallo López,  “Face2ppg: An unsupervised pipeline for blood volume pulse extraction from faces,”  IEEE Journal of Biomedical and Health Informatics, pp. 1–12, 2023\.


11institutetext: Universidade Estadual de Campinas, Limeira SP, Brazil
11email<EMAIL_ADDRESS>
22institutetext: Universidade Estadual de Campinas, Limeira SP, Brazil
22email<EMAIL_ADDRESS>
33institutetext: Universidade Estadual de Campinas, Limeira SP, Brazil
33email<EMAIL_ADDRESS>
# Planning routes in road freight minimizing logistical costs and accident
risks

Gabriel Adam Bilato 11 0000-0002-5427-3958 Cleber Damião Rocco 22
0000-0002-7988-6136 Anibal Tavares de Azevedo 33 2222–3333-4444-5555

###### Abstract

The Vehicle Routing Problem (VRP) has been widely studied throughout its
history as a way of optimizing routes by minimizing distances, and the issue
of risk in VRP has been received less attention, which is essential to
increase transport safety, to reduce accident costs and to improve delivery
reliability. In this way, this paper aims to support decision makers to plan
routes for a road freight company considering both, i.e. logistics cost and
safety. An analytical approach based on statistics was developed in which
official government data of accidents occurrences and data from cargo
insurance companies were used to estimate the risk cost of routes using the
Monte Carlo simulation. The Capacitated Vehicle Routing Problem (CVRP) was
employed and logistics and risk costs were minimized by varying a specific
safety level coefficient and the model generated solutions with safer routes,
reducing risk cost by up to approximately 18%. The accidents probabilities and
risk costs of each route represented values as expected and the main
contributions of this paper is the applicability of the approach to support
decision markers to choose routes considering safety and logistics costs, and
to be a simple and adaptable methodology for any VRP model. In addition Knime
Analytics Platform was also used to estimate the accidents probabilities and
to simplify data exploration, analysis, visualization and interpretation.

###### Keywords:

VRP with risk CVRP Monte Carlo Simulation Knime Analytics Platform.

##  1 Introduction

In an increasingly globalized and connected world in which the population and
urbanization grows over the years, the pressure for more efficient and
sustainable road freight increases due to the greater demand for different
types of products. Road freight plays a fundamental role in global logistics
due to the flexibility of the infrastructure that this segment of transport
offers, allowing a door-to-door service, which is not possible with other
modes [13].

On the other hand, the reliability in road freight depends on some factors
that can be the cause of many accidents, interrupting the supply chain and
generating significant losses. According to the World Health Organization
(WHO) data, accidents costs on average around 3% of the Gross Domestic Product
(GDP) of a country and led to the death of 1.35 million people, being the
eighth leading cause of death all around the world.

Therefore, reducing the accident rate of road freight is an important factor
from a strategic and sustainable point of view, which seeks logistical and
economical development, because when an accident occurs losses can assume
large financial proportions in addition to impact in others different
dimensions. From this point, the need for improvement in the reduction of
losses in road transport stands out [13].

When a route is chosen for the vehicle that will leave a depot to deliver to
other cities, not only the logistics costs or distance should be considered,
but also the measurement of the risks linked to that route. Many studies
consider only the first factor using mathematical models like VRP as a way of
solving it. Risk measurement is addressed in cash-in-transit problems also
through the VRP, which basically is a mathematical model that aims to minimize
the distances traveled with the restriction that the value of the risk of
robberies of heavy trucks during the transport of money is limited by a risk
threshold [21].

The route safety is also discussed in studies of hazardous materials
transportation such as fuels, flammable materials, gases and others, aiming to
reduce social and environmental impacts and increase transport safety by
minimizing the risk factor [18].

VRP has been widely studied throughout its sixty-year history, but still few
studies have taken into account the issue of risk. Recently, researches have
emerged in the areas of cash-in-transit and hazardous materials, but they did
not consider a statistical approach to risk into the models.

Therefore, verifying the applications of the topic risks in VRP and the need
to reduce losses due to accidents, this paper aims to introduce an analytical
approach for road freight through optimization model and statistical analysis
to support the decision making for the choice of routes based on logistic cost
and safety.

In addition to the contributions of this analytical approach are its
simplicity of application to a real problem of a Brazilian road freight
company that daily needs to choose the best routes that consider safety and
costs, as well as their adaptability to other VRP models. Finally, Knime
Analytics Platform was helpful to simplify data exploration, analysis,
visualization and interpretation and to estimate the accidents probabilities.

This paper is organized in five sessions in which the first one introduces the
importance of studying risk in VRP. From the second session, a review and
discussion of the literature which addressed risks in VRP is carried out. In
an analytical approach, the methodology proposed for the study is shown, as
well as the calculations used. Finally, the results are presented in
experimental studies and the conclusion is drawn from this.

##  2 Literature review

###  2.1 Risk in VRP

Vehicle Routing Problems (VRP) have been extensively studied throughout their
history to support real-life applications. Risk and safety in VRP has been
received more attention in applications for the transport of hazardous
materials, whose risk is an accident causing socio-environmental damage, and
cash-in-transit which are related to cargo theft [22].

[14] cited eight risk models that were developed for the optimization of
hazardous materials transportation, whose three main ones are represented by
Table 1. For the first model, the risk ($IP$) is calculated through the
probability of the undesirable occurrence event of each route $i$, while the
second ($PE$) considers only the number of people exposed to risk. In the
traditional model, the risk ($TR$) is a product between the probability of the
undesirable event and its measure of consequence.

To investigate the behavior of these three risk models in VRP, [18] used bi-
objective functions that minimize both distance and accident risk. The results
shows that the Traditional Risk generates the best reduction in total risk but
it shows the worst deviation from the minimum distance when compared to the
other two models. The Accident Probability offers the best trade-off with an
economical goal and it is most appropriate for problems where the consequences
are uncertain. As for the Population Exposed, the data are more easily
acquired and the results are evaluated more intuitively for a decision maker,
but it could only be applied to problems that consider urban areas because for
an environment such as rural areas other factors must be considered.

Model | Equation |
---|---|---
Accident Probability | $IP(r)=\sum_{i\in r}p_{i}$ |  $p_{i}=$ accident probability
Population Exposure | $PE(r)=\sum_{i\in r}D_{i}$ |  $D_{i}=$ population exposure
Tradicional Risk | $TR(r)=\sum_{i\in r}p_{i}*C_{i}$ |  $p_{i}=$ accident probability
|  |  $C_{i}=$ measure of the consequence
Table 1: Models for risk assessment. Adapted from [14].

The elements of each model such as accident probability, consequences, number
of people exposed and others, are defined according to the case is being
studied. [2, 8] , for example, studied the risks in hazardous materials
transport and they considered that the undesirable event would be the accident
whose consequence is related to the number of people exposed to risk. On the
other hand, [21] applied the risk in cash-in-transit routing problem that they
considered the probability of a robbery is proportional to the distance of the
route and, as a consequence, the amount of cash into the truck.

In addition to the elements, the models also vary according to the risk
approach used in VRP. Thus, Table LABEL:tab:table_2 was built to show the case
studied, models and risk elements that were adopted for the calculation.

[12, 19, 23] applied the concept of the traditional model, as proposed by [14]
in which the probability of an accident was used as an undesirable event and
the exposed population as a consequence. [2, 18] also applied the traditional
definition, however it was considered as load dependent, that is, the amount
of load factor is added to the model and varies as deliveries are made. [8] is
also based on the traditional model, but two other factors that interfere in
the driver’s attention are added to the objective function, the Altimetric
Index and the Planimetric Index. The first considers the elevations along the
route while the second is introduced to take into account geometrical
constraints related to the road radius.

[7, 6] calculated the risk in a different way than what has been discussed so
far. In this case, in addition to the accidents probabilities, it also
considered the release probability as a result of the accident, which the
consequences are the number of people exposed, and the truck type and the load
amount have a relevant impact on the risk.

As a derivation of hazardous materials, models for cash-in-transit arise. [21,
22] proposed the traditional method to calculate the risk of robbery. As
already explained, they considered the consequence as equivalent to the amount
of value in transport. [16] also assumed the consequence as the same way and
the distance is proportional to the risk of theft, but added to the model a
factor about the frequency of passing through the same route and the ambushing
probabilities to the vehicle and its success.

Table LABEL:tab:table_2 shows that the studies are concentrated in only two
areas: hazardous materials and cash-in-transit. Talking about other segments
of transport, there are few studies in the literature taking into account
risks in VRP and it is important because there are also significant
consequences or losses in case an accident happens, especially financial when
the values of shipped goods are high.

The VRP model with risks vary according to the objectives of each study. Table
4 summarizes the problem characteristics with the nomenclature presented by
[4]. The symbol “x” is used when the paper considers the characteristics and
Table 3 represents the nomenclatures.

[7, 21] used a mono-objective function which firstly minimized the distances
and than the risk. [2, 6, 19, 23] suggest bi-objective functions that analyze
both logistical costs or distances and route risks. Multi-objectives are
presented by [8, 16, 24] which the first one, in addition to minimize the
distance, weighted the risk by the traditional method (probability of accident
and a consequence) and the number of people exposed.

Generally, the risk factor is analyzed as an objective to be minimized,
however [21] considers it as a constraint which the risk value is limited by a
risk threshold and classified as Risk constrained Cash-in-Transit Vehicle
Routing Problem (RCTVRP). [23] restricts the condition that no vehicles of the
same fleet travel in echelon because when there are two or more vehicles using
the same route as the same time the consequences are considered to be greater
if occurs an accident between them.

Table 2: Risk models proposed in literature. Authors |  Case studied |  Risk model
---|---|---
[24] |  Hazardous Materials |  accident probability * consequence + population exposure
[2, 18] |  Hazardous Materials |  accident probability * population exposure * load amount
[12, 19, 23] |  Hazardous Materials |  accident probability * population exposure
[21] |  Cash-in-Transit |  route length * load amount
[7, 6] |  Hazardous Materials |  accident probability * release probability * route length * load amount * truck type * population exposure
[8] |  Hazardous Materials |  accident probability * population exposure + altimetric index + planimetric index
[16] |  Cash-in-Transit |  ambush probability * theft success probability * route length * load amount * frequency of repeated use of a route
Categories | Sub-categories
---|---
Objective Function (3.10) | Travel time dependent (3.10.1)
Distance dependent (3.10.2)
Implied hazard/risk related (3.10.5)
Others (3.10.6)
Data used (5.1) | Real-world data (5.1.1)
Table 3: Nomenclature proposed by [4]. * Nomenclature presented by [4]. |  |
---|---|---
Authors | VRP | 3.10* | 5.1*
|  | 3.10.1* | 3.10.2* | 3.10.5* | 3.10.6* | 5.1.1*
[2] | VRPTW | x |  | x |  |
[7] | HVRP |  |  | x |  |
[6] | HVRP |  | x | x |  |
[8] | VRPTW | x |  | x | x | x
[12] | MRVRP |  |  | x |  | x
[16] | VRPTW |  | x | x |  |
[18] | CVRP |  | x | x |  |
[19] | VRPTW | x |  | x |  | x
[21] | RCTVRP |  | x |  |  |
[23] | VRPTW |  | x | x |  |
[24] | CVRP |  | x | x | x |
Table 4: Description and characteristics of VRP models.

For the measurement of risk, few studies is addressed on how the data are
explored and, according to [12], it is necessary to integrate real historical
data of accidents and big-data in the formulation of models for the transport
of hazardous materials, however [21] mentions that there is little data
available and [2] does not explore risk measurement due to its complexity and
also states that future studies should deal with this issue.

[8] calculated the accident probability from data obtained by the mobility
agency in Rome, quantified population density through a census data and
measured the infrastructure through the Google Application Programming
Interface (API).

[19] estimated accident rates using data collected from the Institute for
Traffic Accident Research and Data Analysis (ITARDA) and the Ministry of Land,
Infrastructure, Transport and Tourism (MLIT), both from Japan. [16] estimated
the probability of a robber attack using game theory, while to calculate the
success probability it used the multi-criteria decision making.

For a future study, [19] proposed extensions of the model considering such
characteristics for hazardous materials routing problem using real-time
traffic information and considering the effects of infrastructural
characteristics of the road network for future studies.

[5] developed a methodology for calculating the risk of accidents in the
hazardous materials transport which factors that influence the accident
probability as well as their consequences were considered. The factors were
measured from indirect interviews with experts obtaining numerical risk
results for each route through this analysis. On the other hand, it did not
use mathematical models of VRP to optimize routes and it did not consider
statistical analysis.

As much as some studies still try to deal with the use of real data in their
problems, the statistical view in data analysis is not approached in a deeper
way. [15] reviewed some the extensions of the free software Knime Analytics
Platform that could support the analyzes from a database and that provides the
creation of structured workflows. Combined with this, [1] used the Monte Carlo
simulation to assess the losses in economic values for the Pakistani economy
in the event of a transport strike, but in the case of this study it would
relate the losses to road accidents.

###  2.2 Contributions of this paper

  * •

Develop a risk model in VRP that is applied to both the cases studied
presented in Table LABEL:tab:table_2 and to different cases of the road
freight;

  * •

Use real-world data and statistical approach to estimate the accident
probabilities. As Table 4, few studies take into account real-world data and
none of them use a statistical approach.

##  3 Analytical Approach

###  3.1 Description

This study followed the procedures described in the workflow (Figure 1) and
started from the VRP definition that was employed with a set of cities and
roads known by the authors. Then, the parameters were defined by the online
tool [20] to calculate the logistics costs of each arc, which consider fuel
expenses, based on the vehicle’s consumption and its value per liter, and with
tolls, whether there is on the arc.

Figure 1: Workflow to employ this paper metodology.

In parallel, the literature on statistical analysis of risk in road freight
was revised and from [5] and from the data that was found, the approach to
calculate the probabilities and costs related to the risk of accident for each
arc was developed. All collected and processed data used in this study is
available at [3].

Several databases of Brazilian roads were consulted on the web and it was
found that, for the most part, it comes from government agencies whose
information is available for public viewing and among them there are: the
National Transport Confederation (CNT), the Department of Roads and Highways
of the State of Sao Paulo (DER- SP) and the National Department of Transport
Infrastructure (DNIT). Through a load insurance, data was provided regarding
the losses in monetary values that occurred due to accidents between the
periods from January 2018 to March 2021.

The data were processed using the Knime Analytics Platform tool, which
generated the accident probabilities for each arc. Then, from the probability
results, the Monte Carlo simulation was programmed to obtain the costs related
to the risks of the arcs.

The objective function (Equation 1) minimizes logistics and risk-related
costs, and it was weighted by the $\alpha$ parameter whose values vary between
0 and 1 and which consists of assigning weight to safety during the
optimization.

After defining the objective function and the parameters of the VRP, the
mathematical model was implemented in Python and the results were generated by
CBC solver. The decision maker could evaluate the routes and the values of
each objective function component, logistics cost and risk cost, and for the
total that is the sum of them.

The security level $\alpha$ must be adjusted by the decision maker to assess
whether the results are suitable to the case. Depending on the cargo type or
its value, $\alpha$ may have to be adjusted in order to have a greater or
lesser level of safety prioritization of the routes.

Therefore, this evaluation is necessary for the decision maker to consider
logistics costs and security, if the result is not adequate, a new change of
$\alpha$ must be carried out until the solution fits to the best choice of the
decision maker.

###  3.2 The VRP model

The capacitated VRP (CVRP) is employed in a real problem of a transportation
company and the arcs are defined through the indirect graph $G=(N,E)$. The
problem presents a single depot that is located in Limeira/SP. Two vertices
are created to represent exit and arrival in the depot, respectively
($\\{0,n+1\\}$). Set $C=\\{1,...,n\\}$ represents the delivery points in nine
cities ($n=9$). The total number of vertices is represented by
$N=C\cup\\{0,n+1\\}$. Set ($K=\\{k_{1},k_{2},k_{3}\\}$) is the vehicles with
equal capacity $q$. The map indicated in Figure 2 illustrates both the depot
and all the delivery points that the carrier must carry out.

The expressions of the mathematical model are presented next. Firstly it is
defined the sets.

$N=C\cup\ \\{0,n+1\\},C=\\{1,...,n\\},E=\\{(i,j):i,j\in N,i\neq j,i\neq
n+1,j\neq 0\\}$

$minz=(1-\alpha)\sum_{k\in K}\sum_{(ij)\in E}c_{ij}X_{ijk}+\alpha\sum_{k\in
K}\sum_{(ij)\in E}r_{ij}X_{ijk}$ (1)

$\sum_{k\in K}\sum_{j\in E}X_{ijk}=1,\forall i\in C$ (2)

$\sum_{i\in E}d_{i}\sum_{j\in E}X_{ijk}\leq q,\forall k\in K$ (3)

$\sum_{j\in E}X_{0jk}=1,\forall k\in K$ (4)

$\sum_{i\in E}X_{ihk}-\sum_{j\in E}X_{hjk}=0,\forall h\in C,k\in K$ (5)

$\sum_{i\in E}X_{i,n+1,k}=1,\forall k\in K$ (6)

$u_{ik}-(n+1)X_{ijk}\leq u_{jk}-n,\forall(i,j)\in E,k\in K$ (7)

$X_{ijk}\in\\{0,1\\},\forall(i,j)\in E,k\in K$ (8)

Parameters: $c_{ij}$: logistics cost; $r_{ij}$: Risk cost; $\alpha$: security
level; $d_{i}$: demand of node $i$; $q$: vehicle capacity; $X_{ijk}$: binary
variable.

The Equation (1) is the objective function that minimizes logistics $c_{ij}$
and risks $r_{ij}$ costs. The Equation (2) describes each arc must receive
only one vehicle. The vehicle capacity constraint is represented by the
Expressions (3). Equations (4) and (6) show every vehicle must leave and
arrive at the depot, respectively. The flow restriction for each node is
represented by the Equation (5). Finally, the sub-tour elimination is
indicated by the Constraints (7) and the binary variables are defined by
Expression (8).

Figure 2: Depot in red and delivery points in blue.

Expressions (9) ensure a strong formulation to eliminate sub-tour because of
its LP relaxation but the number of these constrains could be too high
($2^{n}$) to the model. Because of this, it was used cut callbacks and lazy
constraints to insert only constrains which violated the model and it is not
necessary to use $2\leq|S|\leq n$ in the model [17].

$\sum_{ij\in S}{X_{ijk}}\leq|S|-1,\forall S\subseteq C,k\in K$ (9)

Where: $S$ is a set of sub-tour.

The cut callbacks are used only to improve the LP relaxation but not to define
feasible solutions, which need to define by the initial formulation. So, it is
included a weak sub-tour elimination constraints presented by Expression (7)
in the initial model and then add Constraints (9) as cuts.

In this way, Python MIP ([17]) package was introduced to the model because it
is possible to eliminate sub-tour with cut callbacks and lazy constraints that
makes it more efficient. The free solver CBC was used to optimize this problem
and it was solved in 44 seconds for all twenty different values of $\alpha$
resulting in 363 variables and 289 constrains for each instance.

###  3.3 Calculating the risk cost $r_{ij}$

As already mentioned, the accidents probabilities $Paccident_{ij}$ were
generated for each arc ij by Knime Analytics Platform, according to the
workflows represented by the Figures 3, 4 and 5 and Equations (10), (11),
(12), (13), (14), (15), (16), (17) e (18).

At this first moment, it was necessary to estimate a general probability
($Pgeneral$) of accidents occurring on any road in Brazil according to the
workflow of the Figure 3. Data was collected from the free websites of [10,
11] and from the article [9]. [11] provides the average volume $V$ of all
vehicles that travel daily on federal roads, while [10] extracted the
percentage $P_{sp}$ of heavy vehicles $HV_{sp}$ over the total $V_{sp}$ that
circulates in Sao Paulo State roads that was calculated by Equation (10) and
assumed that the percentage in federal roads as the same. From this point of
view, Equation (11) resulted in the amount of heavy vehicles $HV$ that is used
in Equation (12) with the number of accidents $N_{accidents}$, extracted from
[9], and then $Pgeneral$ was found.

Figure 3: Workflow to calculate $Pgeneral$.

$P_{sp}=HV_{sp}/V_{sp}$ (10)

$HV=P_{sp}.V$ (11)

$Pgeneral=\frac{N_{accidents}}{HV}.100\%$ (12)

The factors considered to the calculation of $r_{ij}$ were: the types of roads
and the traffic of heavy vehicles. The first is considered because in Brazil
there are several types of roads that show different safety levels. The
Accident Panel Report prepared by [9] breaks it into five categories (
$T=\\{t1,...,t5\\}$) as presented by Table 5. It is also shown that the number
of deaths per hundred accidents was extracted from this report and it is
considered in the calculation for the risk of accidents.

Road type | Death rate per 100 accidents
---|---
two lanes two way road with central safety lane | 12.3
two lanes two way road with central barrier | 8.5
two lanes two way road with central line | 18.0
Single lane one way road | 11.9
Single lane two way road | 22.3
Table 5: Death rate per type of road [9].

The flow of heavy vehicles was obtained from [10] by speed radars installed on
the roads and it was considered as directly proportional to the accidents
probabilities because two roads with the same characteristics but one have a
bigger flow than other so the first has greater chances of an accident
occurring.

The indexes $it_{h}$ and $iv_{h}$ represents, respectively, the types of road
and the flow of vehicles were calculated according to the workflow of the
Figure 4 and where $h\in H$ which means that road $h$ is on the set $H$ of
problems roads. The data was collected from [9, 10]. First, it was necessary
to find $\bar{x}$ and $\bar{y}$ by the Equations (13) and (14) that represent,
respectively, the average flow of vehicles $x_{h}$ running on the twelve roads
of the problem $N_{h}=12$ and the average death rate per 100 accidents $y_{t}$
among the five types of roads $N_{t}=5$. Then, the indexes $iv_{h}$ and
$it_{h}$ were calculated by the Equations (15) and (16), which basically
consists if $iv_{h}$ or $it_{h}$ is greater than 1.0, the accident probability
on the road $h$ will be greater than the general probability ($P_{general}$),
and otherwise if the indices are less than 1.0.

$\bar{x}=\frac{\sum_{h\in H}x_{h}}{N_{h}}$ (13)

$\bar{y}=\frac{\sum_{t\in T}y_{t}}{N_{t}}$ (14)

$iv_{h}=1+\frac{x_{h}-\bar{x}}{\bar{x}}\ ,\ \forall h\in H$ (15)

$it_{h}=1+\frac{y_{h}-\bar{y}}{\bar{y}}\ ,\ \forall h\in H$ (16)

Where $x_{h}$ means the flow of vehicles represented by road $h$ and $y_{h}$
the death rate of the type of road $h$.

Figure 4: Workflow to calculate the indexes $iv_{h}$ e $it_{h}$.

In some arcs, the vehicle may pass through more than one road ($h$), e. g.,
the arc Limeira-Cosmópolis has two roads $h_{1}$=SP330 and $h_{2}$=SP133 whose
flows and characteristics are different. Thus, it is necessary a index
$e_{ij}$ that is weighted by $iv_{h}$, $it_{h}$ and $l_{h}$, and represented
by the Equation (17). Where $l_{h}$ is the length that the truck travels in
each road $h$ of the arc $ij$ and $l_{ij}$ represents the total length of the
arc $ij$.

$e_{ij}=\frac{\sum_{h\in H}iv_{h}.it_{h}.l_{h}}{l_{ij}}\ ,\ \forall(i,j)\in E$
(17)

Finally, Equation (18) describes the accident $Paccident_{ij}$ occurring among
$ij$. The workflow of the Figure 5 shows how $Paccident_{ij}$ and $e_{ij}$
were found.

Figure 5: Workflow to calculate $e_{ij}$ and $Paccident_{ij}$.

$Paccident_{ij}=Pgeneral.e_{ij}\ ,\ \forall(i,j)\in E$ (18)

After to find $Paccident_{ij}$, it is possible to estimate $r_{ij}$ by Monte
Carlo simulation. This was possible through data provided by the load
insurance, which collected the percentages of accidents divided into intervals
of losses in load values according to Table 6.

Range of values | occurrence
---|---
$ 0.01 to $ 200,000.00 | 37.91%
$ 200,000.00 to $ 300,000.00 | 24.17%
$ 300,000.00 to $ 500,000.00 | 19.91%
$ 500,000.00 to $ 1,000,000.00 | 16.11%
$ 1,000,000.00 or more | 1.90%
Table 6: Percentage of accidents divided by the range of losses in load
values.

The Figure 6 illustrates an example of how the probabilities were distributed.
The maximum load value for each range and the cost to the road freight company
was considered as being 1% of its value, a deductible that load insurances
usually charge. Thus, the occurrence of the event in the range between $0.01
and R$200,000.00, the value to be considered will always be the highest of the
range, which in this case will be $200,000.00 and deductible cost for the
carrier would be $2,000.00.

Figure 6: Accident probabilities and its costs to Monte Carlo Simulation.

Also through Figure 6 it is possible to verify the accumulated percentage
values, between 0 and 1, for each accident cost on the right. This will be
important for the Monte Carlo simulation, which at each iteration selects a
random value between 0 and 1 that will correspond to a accident cost. For
example, according to Figure 6 each percentage range is equivalent to its
cost, so any value selected in the range between 0 and 0.990971 will
correspond to a accident cost equal to $0.00.

In this way, 1,000,000 iterations were performed for each arc of the problem
and the average of accident costs was calculated and it generates $r_{ij}$
that will be used in the objective function of this VRP. This number of
iterations was chosen because the accidents probabilities are very low and
thus the values of $r_{ij}$ present better convergence. However, if the
iterations are above the established, the resolution time becomes longer and
therefore, for this problem, 1,000,000 is an ideal number.

##  4 Results and Discussions

###  4.1 Probabilities and costs of risks

Figures 7 and 8 represent the results for $Paccident_{ij}$ and $r_{ij}$,
respectively. After performing analyses, it was observed that $Paccident_{ij}$
and $r_{ij}$ obtained are in line with what was expected. When comparing the
arcs of the same type of road as Piracicaba-Santa Bárbara and Limeira-Mogi
Mirim, it was verified that $Paccident_{ij}$ for the first (1.91455 %) is
greater than the second (0.147464 %) as well as for $r_{ij}$ which is $ 788.70
and $ 61.61, respectively. It was expected because the vehicles flow on the
Piracicaba-Santa Barbara arc (6,943 heavy vehicles) is greater than the other
(535 heavy vehicles).

Figure 7: Accidents Probabilities $Paccident_{ij}$ in %. Figure 8: Risk cost
$r_{ij}$ in $.

When comparing arcs that present similar or close vehicle flow such as Mogi
Mirim-Araras and Mogi Mirim-Limeira, it is noted that $Paccident_{ij}$ for the
first (0.300835 %) is greater than the second (0, 147464 %) as well as for
$r_{ij}$ which is $ 125.66 and $ 56.95. And this is due to the fact that the
road that connects Mogi Mirim and Araras is a single lane two way road,
according to the nomenclature of [9], which has the highest death rate among
all type of roads.

Other analyzes like this were also carried out and the same conclusions were
reached. In this way, it is possible to state that the methodology followed to
find $Paccident_{ij}$ and $r_{ij}$ was satisfactory, since consistent results
were found according to the results obtained.

###  4.2 Optimization results

Figure 9 represents the graph with the results of each parcel, logistics and
risk cost, and the sum between them for the optimization varying $\alpha$.
Note that for $\alpha=0$, the logistic cost assumes the minimum value when
compared to others $\alpha$, but the risk is the highest. When considering a
greater weight of security during the optimization, that is, when increasing
$\alpha$, the risk cost starts to decrease and the logistic cost increases.
This occurs because the model starts to prioritize arcs with lower risks and
thus reducing the concern with the cost of tolls and fuel.

It is verified by Figure 9 that for this problem a variation is perceived in
$\alpha=0.15$ which the logistic cost suffers an increase from $ 729.70 to
$834.36 while the risk decreases from $3832.44 to $3175.29 representing a
decrease of approximately 17.15 %. Between $\alpha=0.20$ and $\alpha=0.75$,
the minimum logistics costs remain at $851.38 and risks at $3106.47, which
further increases the level of safety fact.

It is important to a decision maker to see it because the choice of routes
will depend on what level of security it wants to work for its fleet. If
security is considerable in the process of the company, it is important to
work with $\alpha\geq 0.15$ but if the logistics cost is still relevant, the
level of security should be $\alpha\leq 0.75$, because for $\alpha\geq 0.80$
the logistics cost will reach R$ 966.34 and the risk R$ 3070.95 which allows
us to say that, due to the first parcel, there will be a considerable increase
of approximately 13.50 % and the second reduce only 1.1 %, it would not be
worth working in this range.

Figure 9: Results of $c_{ij}$, $r_{ij}$ e $z$

The routes were also evaluated and it is represented by Figures 10(a), 10(b),
10(c) and 10(d) which each delivery point is identified with a marker and
letter, referring to the sequence of deliveries made by each truck. It is also
noted that there are different colors for the markers that identify which
truck is carrying out the delivery, facilitating the evaluation of the
results. For example, the markers in red represent truck 1, in black truck 2,
in green truck 3 and in blue the warehouse.

(a) $\alpha=0,00$

(b) $\alpha=0,15$

(c) $\alpha=0,20$

(d) $\alpha=1,00$

Figure 10: Routes obtained for different values of $\alpha$.

Only routes were printed from $\alpha$ being 0.00, 0.15, 0.20 and 1.00.
According to the graph in Figure 9, these are the points that show variations.
For $0.10\leq\alpha\leq 0.15$ there were some variations, the main one being
eliminating the Cosmópolis-Limeira ($r_{ij}=637.75$ red arc in Figure 10(a))
and adding Mogi Mirim-Limeira ( $r_{ij}=61.61$ green arc in the Figure 10(b))
and thus reducing the risk, in this case alone, by approximately 85% in
relation to the total amount that was reduced for this comparison.

The arc Mogi Mirim-Limeira or vice versa, represented by green arc in Figure
10(b), it started to be added as soon as $\alpha$ increases and it occurs
because its risk cost is one of the lowest. Its inclusion is the one that most
impacted the minimization of risk, therefore for $\alpha\geq 0.20$ the risk
cost decreases only approximately to 1%, as this arc has already been
considered.

When analyzing $\alpha=0.20$, it was noticed that the arc Araras-Holambra
(green arc in the Figure 10(c)) was included ($r_{ij}=182.59$) but a part of
it passes through the same road with origin in Araras and destination Limeira
($r_{ij}=583.51$), represented by orange arc in Figure 10(a). This means that
to leave Araras and go to Holambra, the truck initially travels along a less
safe road, but then in the most part of the arc is on low risk roads, which
makes $r_{ij}$ to have a lower value and this could be a limitation for the
method.

##  5 Conclusion

This paper consisted of inserting the issue of route safety in the vehicle
routing process of a road freight company in order to help the decision maker
to select the best routes that minimize both the distance and the risk of
accidents.

A method was developed that considers the statistical analysis to estimate the
accidents probabilities for each arc and the costs related to the risks of
accidents from the Monte Carlo simulation. The results obtained were coherent,
converging to what was expected to the problem.

Through a mathematical model of VRP, logistics costs and risks were minimized
and the results were analysed for each part of the objective function and the
routes obtained for different values of a risk coefficient alfa ($\alpha$).

According to the outcomes displayed in Figure 9, it was identified that as the
safety factor increases, the risk-related costs decrease, which is more
noticeable when $0.10\leq\alpha\leq 0.20$. It was also noticed that, when
comparing the routes, it was identified that the model started to incorporate
security routes as results.

A limitation observed in the proposed method is for two trips passing through
the same road, the accidents probabilities were different and this can be
explained because in one trip the truck would be on the more dangerous road
for longer than the other, interfering estimation process.

However, it is possible to analyze that the method worked in a positive way by
verifying the accidents probabilities and risk cost and it can help the
decision maker of a road freight company to select the best routes considering
distance and accident risk. In addition, the whole approach developed here is
simple and adaptable to any VRP model and can be used by any company for free.

Finally Knime Analytics Platform helps to deal with the use of real data in
this paper simplifying data exploration, analysis, visualization and
interpretation.

For future works, it is relevant to develop an approach that considers the
risk of load theft in VRP and based on statistical analysis. In addition, it
is necessary to add that during the day accident probability and risk of theft
could vary because some variables, as traffic flow, changes according the time
and this will help road freights and load insurers to make decisions about the
time that a truck could pass at certain road.

## References

  * [1] Ali, Y., Bilal, M., Sabir, M.: Impacts of transport strike on Pakistan economy: An inoperability Input-Output model (IIOM) approach. Research in Transportation Economics 90(December 2019), 100860 (2021). https://doi.org/10.1016/j.retrec.2020.100860
  * [2] Androutsopoulos, K.N., Zografos, K.G.: A bi-objective time-dependent vehicle routing and scheduling problem for hazardous materials distribution. EURO Journal on Transportation and Logistics 1(1-2), 157–183 (2012). https://doi.org/10.1007/s13676-012-0004-y
  * [3] Bilato, G.A.: (2022), www.github.com/GabrielBilato/paper_riskVRP_2022
  * [4] Braekers, K., Ramaekers, K., Van Nieuwenhuyse, I.: The vehicle routing problem: State of the art classification and review. Computers and Industrial Engineering 99, 300–313 (2016). https://doi.org/10.1016/j.cie.2015.12.007
  * [5] Branko Milovanović: Methodology for establishing the routes for transportation of dangerous goods on the basis of the risk level - Case study: City of Belgrade. Scientific Research and Essays 7(1) (2012). https://doi.org/10.5897/sre11.655
  * [6] Bula, G.A., Murat Afsar, H., Gonzalez, F.A., Prodhon, C., Velasco, N.: Bi-objective vehicle routing problem for hazardous materials transportation. Journal of Cleaner Production 206, 976–986 (2019). https://doi.org/10.1016/j.jclepro.2018.09.228
  * [7] Bula, G.A., Gonzalez, F.A., Prodhon, C., Afsar, H.M., Velasco, N.M.: Mixed Integer Linear Programming Model for Vehicle Routing Problem for Hazardous Materials Transportation. IFAC-PapersOnLine 49(12), 538–543 (2016). https://doi.org/10.1016/j.ifacol.2016.07.691
  * [8] Carrese, S., Cuneo, V., Nigro, M., Pizzuti, R., Ardito, C.F., Marseglia, G.: Optimization of downstream fuel logistics based on road infrastructure conditions and exposure to accident events. Transport Policy (xxxx) (2019). https://doi.org/10.1016/j.tranpol.2019.10.016
  * [9] CNT: Acidentes Rodoviários: Estatísticas envolvendo caminhões. Confederação Nacional de Transportes (2019), https://cnt.org.br/acidentes-rodoviarios-caminhoes
  * [10] DER-SP: Contagem Volumétrica Classificatória - VDM (2018), www.der.sp.gov.br/WebSite/MalhaRodoviaria/PesquisaRodovias.aspx
  * [11] DNIT: Plano Nacional de Contagem de Tráfego (2020), www.servicos.dnit.gov.br/dadospnct/Modelagem
  * [12] Du, J., Li, X., Yu, L., Dan, R., Zhou, J.: Multi-depot vehicle routing problem for hazardous materials transportation: A fuzzy bilevel programming. Information sciences 399, 201–218 (2017)
  * [13] Engström, R.: The Roads’ Role in the Freight Transport System. Transportation Research Procedia 14, 1443–1452 (2016). https://doi.org/10.1016/j.trpro.2016.05.217
  * [14] Erkut, E., Ingolfsson, A.: Transport risk models for hazardous materials: Revisited. Operations Research Letters 33(1), 81–89 (2005). https://doi.org/10.1016/j.orl.2004.02.006
  * [15] Fillbrunn, A., Dietz, C., Pfeuffer, J., Rahn, R., Landrum, G.A., Berthold, M.R.: KNIME for reproducible cross-domain analysis of life science data. Journal of Biotechnology 261(February), 149–156 (2017). https://doi.org/10.1016/j.jbiotec.2017.07.028
  * [16] Ghannadpour, S.F., Zandiyeh, F.: An adapted multi-objective genetic algorithm for solving the cash in transit vehicle routing problem with vulnerability estimation for risk quantification. Engineering Applications of Artificial Intelligence 96(September), 103964 (2020). https://doi.org/10.1016/j.engappai.2020.103964
  * [17] Haroldo G. Santos, Toffolo, T.A.: Mixed Integer Linear Programming with Python pp. 1–58 (2019), https://buildmedia.readthedocs.org/media/pdf/python-mip/latest/python-mip.pdf
  * [18] Holeczek, N.: Analysis of different risk models for the hazardous materials vehicle routing problem in urban areas. Cleaner Environmental Systems 2(February), 100022 (2021). https://doi.org/10.1016/j.cesys.2021.100022
  * [19] Pradhananga, R., Taniguchi, E., Yamada, T., Qureshi, A.G.: Bi-objective decision support system for routing and scheduling of hazardous materials. Socio-Economic Planning Sciences 48(2), 135–148 (2014). https://doi.org/10.1016/j.seps.2014.02.003
  * [20] Qualp: (2022), www.qualp.com.br/
  * [21] Talarico, L., Sörensen, K., Springael, J.: Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem. European Journal of Operational Research 244(2), 457–470 (2015). https://doi.org/10.1016/j.ejor.2015.01.040
  * [22] Talarico, L., Springael, J., Sörensen, K., Talarico, F.: A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing problem. Computers and Operations Research 78, 547–556 (2017). https://doi.org/10.1016/j.cor.2016.04.003
  * [23] Wang, N., Zhang, M., Che, A., Jiang, B.: Bi-Objective Vehicle Routing for Hazardous Materials Transportation with No Vehicles Travelling in Echelon. IEEE Transactions on Intelligent Transportation Systems 19(6), 1867–1879 (2018). https://doi.org/10.1109/TITS.2017.2742600
  * [24] Zheng, B.: Multi-objective vehicle routing problem in hazardous material transportation. ICLEM 2010: Logistics for Sustained Economic Development - Infrastructure, Information, Integration - Proceedings of the 2010 International Conference of Logistics Engineering and Management 387, 3139–3145 (2010). https://doi.org/10.1061/41139(387)438


# Interval chains and completeness in ultrapowers of ordered sets

Zoltán Boros  and  Péter Tóth  Institute of Mathematics, University of
Debrecen, 4002 Debrecen, Pf. 400, Hungary<EMAIL_ADDRESS>Institute
of Mathematics, University of Debrecen, 4002 Debrecen, Pf. 400, Hungary
<EMAIL_ADDRESS>
###### Abstract.

The ultrapower $T^{\ast}$ of an arbitrary ordered set $T$ is introduced as an
infinitesimal extension of $T\,$. It is obtained as the set of equivalence
classes of the sequences in $T\,$, where the corresponding relation is
generated by an ultrafilter on the set of natural numbers. It is established
that $T^{\ast}$ always satisfies Cantor’s property, while one can give the
necessary and sufficient conditions for $T$ so that $T^{\ast}$ would be
complete or it would fulfill the open completeness property, respectively.
Namely, the density of the original set determines the open completeness of
the extension, while independently, the completeness of $T^{\ast}$ is
determined by the cardinality of $T\,$.

###### Key words and phrases:

ordered sets, interval chains, Cantor’s property, completeness, ultrafilter,
ultrapower

###### 2020 Mathematics Subject Classification:

06A05,26E30

Research of Z. Boros has been supported by the K-134191 NKFIH Grant and the
2019-2.1.11-TÉT-2019-00049 project. Projects no. 2019-2.1.11-TÉT-2019-00049
and K134191 have been implemented with the support provided from the National
Research, Development and Innovation Fund of Hungary, financed under the TÉT
and K 20 funding schemes, respectively.
Research of P. Tóth has been supported by the EFOP-3.6.1-16-2016-00022
project. The project was co-financed by the European Union and the European
Social Fund.

##  1\. Introduction

A well known statement from the theory of ordered fields is that an ordered
field is complete if and only if it simultaneously fulfills the Archimedean
property and Cantor’s property. To demonstrate the independence of these
properties, one needs to construct an ordered field which fulfills Cantor’s
property but is not complete. This question is usually treated in the
framework of non-standard analysis, for instance in the works of Stroyan and
Luxemburg [6], [4].

However in the above cited publications one can also find an idea for a
construction that needs only standard tools. This idea is the concept of
ultrapowers: Let us choose an adequate family of subsets of the set of natural
numbers called ultrafilter, and then use it to define an equivalence relation
on the set of all sequences of the elements of a given set $R$. This provides
a partition, and the set of the equivalence classes is called the ultrapower
of $R$. After introducing this concept, the authors proceed using mainly non-
standard techniques, also when it comes to show the properties of the
ultrapower. We note that the result of this method is an extension of the
original set, since the classes of the constant sequences can be considered as
representatives of the original elements.

The aforementioned works contain only the main ideas without the technical
parts, but in the recent publication [2] of Corazza, a detailed construction
of the ultrapower of $\mathbb{Q}$ (denoted by $\mathbb{Q}^{\mathbb{N}}/U$) is
displayed. One of the main objectives of his work is to construct a non-
archimedean ordeded field that fulfills Cantor’s property (in [2] it is
referred as Nested Intervals Property). As mentioned above, such a
construction provides an ordered field with the Cantor property which is not
complete.

Not surprisingly, only the ordering of the ultrapower plays an important role
during the investigation of these two order-related properties: completeness
and the Cantor property, while the field operations are irrelevant at that
point. Actually this fact motivates us to generalize these constructions,
introducing the ultrapower of an arbitrary ordered set $T$, and investigating
Cantor’s property and completeness in its extension $T^{\ast}$.

We may note that while ultrafilters play central role in all of the
constructions cited before, the definition of them is not completely coherent.
In fact the ultrafilter has to fulfill some conditions which ensure that the
extension is proper (not trivial), but these conditions do not appear in the
classical definition of the ultrafilter, e.g. in the monograph of Jech [3].
Hence in [4] and [6] a so-called free ultrafilter is used, while in [2] a
nonprincipal ultrafilter is used. The main inconvenience with these special
ultrafilters is to prove their existence – typically it is done by using
Zorn’s lemma. Therefore we find it useful to revisit this question, and define
the concept of an ultrafilter in such a way that it would be suitable for our
construction, and its existence would follow relatively easily from Tarski’s
classical existence theorem for ’ordinary’ ultrafilters (which may be found in
[3, Theorem 7.5]).

Our process of showing Cantor’s property for the ultrapower sometimes
resembles Corazza’s methods, although at one point the fact that we start from
an arbitrary ordered set makes a significant difference. Namely, in [2] it is
shown that in $\mathbb{Q}^{\mathbb{N}}/U$ the intersection of a chain of
countably many open intervals is nonempty. This property is referred to as
open completeness, and it clearly implies both Cantor’s property and the lack
of completeness. In our more abstract setting it is reasonable to investigate
these properties separately. Namely, starting from an ordered set $T\,$, we
shall prove that $T^{\ast}$ always satisfies Cantor’s property, while we can
give the necessary and sufficient conditions for $T$ so that $T^{\ast}$ would
be complete or it would fulfill the open completeness property, respectively.
Namely, the density of the original set determines the open completeness of
the extension, while independently, the completeness of $T^{\ast}$ is
determined by the cardinality of $T\,$.

##  2\. Particular properties of ordered sets

In this section we collect the basic concepts for ordered sets that are in the
focus of this paper.

As usual, we call a nonempty set $X$ equipped with a relation $\leq$ (on $X$)
an ordered set if the relation $\leq$ is reflexive, anti-symmetric,
transitive, and linear (i.e., $x\leq y$ or $y\leq x$ for all $x,y\in X$).

Once the relation $\leq$ on $X$ is given, we shall also use the relations
$\geq\,$, $<$ and $>$ in the usual sense.

We shall use the concepts of lower/upper bound, minimum/maximum (denoted by
$\mathrm{min}$ and $\mathrm{max}\,$, respectively), a set being bounded from
below/above, least upper bound ($\mathrm{sup}$) and greatest lower bound
($\mathrm{inf}$) in the usual sense as well (cf. [3, Definition 2.2]).

######  Definition 1.

An ordered set $(X,\leq)$ is called complete if every nonempty subset of $X$,
that is bounded from above, has a least upper bound.

It is well known that the ordered set $(X,\leq)$ is complete if, and only if,
every nonempty subset of $X$, that is bounded from below, has a greatest lower
bound (a proof in an abstract setting can be found, for instance, in [1,
Theorem 4.6]).

We will define intervals as particular subsets of an ordered set $(X,\leq)$ in
the usual way. For example, if $a,b\in X$ such that $a<b\,$, let
$[a,b[=\\{\,x\in X\,:\,a\leq x<b\,\\}$.

We call a sequence $(I_{n})$ of non-empty intervals an interval chain if
$I_{n+1}\subset I_{n}$ for every $n\in\mathbb{N}\,$. We can describe Cantor’s
property and the open completeness of an ordered set $X$ by the phenomena that
the intersection of an arbitrary interval chain of closed, respectively, open
intervals is non-empty.

######  Definition 2.

We say that an ordered set $X$ satisfies Cantor’s property if

$\bigcap_{n\in\mathbb{N}}[a_{n},b_{n}]\neq\emptyset$

for any sequences $(a_{n}),(b_{n}):\mathbb{N}\rightarrow X$ fulfilling

$a_{k}\leq a_{k+1}\leq b_{k+1}\leq b_{k}$

for every $k\in\mathbb{N}\,$.

######  Definition 3.

We say that an ordered set $X$ is open complete if

$\bigcap_{n\in\mathbb{N}}\,]a_{n},b_{n}[\,\neq\,\emptyset$

for any sequences $(a_{n}),(b_{n}):\mathbb{N}\rightarrow X$ fulfilling

$a_{k}\leq a_{k+1}<b_{k+1}\leq b_{k}$

for every $k\in\mathbb{N}\,$.

Finally, we introduce the concept of density in ordered sets.

######  Definition 4.

We say that an ordered set $X$ is dense everywhere if, for any $a,b\in X$
fulfilling $a<b$, there exists $c\in X$ such that $a<c<b$.

##  3\. An extension of ordered sets

###  3.1. Ultrafilter

We introduce the concept of ultrafilter. For the power set of an arbitrary set
$X$ we will use the notation $\mathcal{P}(X)$, i.e. the elements of
$\mathcal{P}(X)$ are the subsets of $X$.

######  Definition 5.

Let $\mathbf{J}$ be an infinite set. The nonempty family of sets
$\mathcal{U}\subset\mathcal{P}(\mathbf{J})$ is called a filter on
$\mathbf{J}$, if

  * (1)

$K\in\mathcal{U}$ and $K\subset L\subset\mathbf{J}$ implies $L\in\mathcal{U}$,

  * (2)

$K,L\in\mathcal{U}$ implies $K\cap L\in\mathcal{U}$,

  * (3)

$K\in\mathcal{U}$ implies that $K$ is infinite.

Moreover, $\mathcal{U}$ is called an ultrafilter if it is a filter and

  * (4)

if $K\subset\mathbf{J}$, then $K\in\mathcal{U}$ or $\mathbf{J}\setminus
K\in\mathcal{U}$ holds.

######  Remark 1.

In many works (such as [4] or [3]) filters and ultrafilters are defined on
arbitrary sets and not particularly infinite ones. In that general case
assumption (3) is replaced by the weaker condition

  * (3’)

$\emptyset\notin\mathcal{U}$.

In that weaker sense it holds that any filter can be extended to an
ultrafilter (see [3, Theorem 7.5]). Using this result we prove the following
statement.

######  Theorem 1.

Let $\mathbf{J}$ be an infinite set and let $K\subset\mathbf{J}$ be also
infinite. Then there exists an ultrafilter
$\mathcal{U}\subset\mathcal{P}(\mathbf{J})$ such that $K\in\mathcal{U}$.

###### Proof.

Let us define the so-called Fréchet-filter:

$\mathcal{F}=\\{S\subset\mathbf{J}\ |\ \mathbf{J}\setminus S\mbox{ is
finite.}\\}$

It is easy to see that $\mathcal{F}$ is indeed a filter. Let us define another
subset of $\mathcal{P}(\mathbf{J})$:

$\mathcal{M}=\\{M\subset\mathbf{J}\ |\ \exists L\in\mathcal{F}\ :\ K\cap
L\subset M\\}.$

Now we show that $\mathcal{M}$ is a filter (in the weaker sense). Let $M,N$ be
arbitrary sets in $\mathcal{M}$, thus there exist
$L_{M}\,,L_{N}\in\mathcal{F}$ such that $K\cap L_{M}\subset M$ and $K\cap
L_{N}\subset N$.

  * (1)

If $M\subset S$ then $K\cap L_{M}\subset M\subset S$, so $S\in\mathcal{M}$.

  * (2)

$K\cap(L_{M}\cap L_{N})=(K\cap L_{M})\cap(K\cap L_{N})\subset M\cap N$, and as
$L_{M}\cap L_{N}\in\mathcal{F}$, it also holds that $M\cap N\in\mathcal{M}$.

  * (3’)

Assume $\emptyset\in\mathcal{M}$, which means $K\cap L=\emptyset$ for some
$L\in\mathcal{F}$. But this would imply $K\subset\mathbf{J}\setminus L$ and
that is impossible, since $K$ is infinite and $\mathbf{J}\setminus L$ is
finite.

Notice that $\mathcal{F}\subset\mathcal{M}$ trivially holds. Now $\mathcal{M}$
can be extended to an ultrafilter $\mathcal{U}$ (again in the weaker sense).
However $\mathcal{U}$ is an ultrafilter in our restrictive sense, too. Indeed,
if $F\in\mathcal{U}$ for some finite subset $F$, then $\mathbf{J}\setminus
F\notin\mathcal{U}$ which contradicts $\mathbf{J}\setminus F\in\mathcal{F}$. ∎

As a corollary of this statement, we get that there exists an ultrafilter on
the set of natural numbers. Finally we emphasize that the existence of an
appropriate ultrafilter on $\mathbb{N}$ can be proven in several, slightly
different ways. However this often requires the introduction of further
definitions such as free ultrafilter (in [4]) or nonprincipal ultrafilter (in
[2]).

###  3.2. Ultrapower of an ordered set

In the next step we construct a so called ultrapower of any ordered set $T$.
The existence of an ultrafilter on the set of natural numbers provides us a
way to define an equivalence relation on the set of all sequences of elements
of $T$, in such manner that an adequate order on the equivalence classes would
generate an ordered set. As it is common in the literature, we will use an
asterisk (∗) to denote the operation that assigns its ultrapower to the
original ordered set.

In the subsequent sections let $T$ be an ordered set and $\mathcal{U}$ be an
ultrafilter on $\mathbb{N}$.

Let $\mathcal{T}=\\{(a_{n})\ |\ (a_{n}):\mathbb{N}\rightarrow T\\}$ denote the
set of all sequences of elements of $T$.

######  Proposition 1.

Let us define the relation $\sim\ \subset\mathcal{T}\times\mathcal{T}$ in the
following way:

$(a_{n})\sim(b_{n})\Longleftrightarrow\\{n\in\mathbb{N}:a_{n}=b_{n}\\}\in\mathcal{U}.$

Then $\sim$ is an equivalence relation. Furthermore, let us denote the set of
the equivalence classes by $T^{\ast}$, while the class of an element
$(a_{n})\in\mathcal{T}$ be denoted by $\overline{(a_{n})}\,$. The relation
$\leq\ \subset T^{\ast}\times T^{\ast}$, given by

$\overline{(a_{n})}\leq\overline{(b_{n})}\Longleftrightarrow\\{n\in\mathbb{N}:a_{n}\leq
b_{n}\\}\in\mathcal{U}\,,$

is well-defined, and $(T^{\ast},\leq)$ is an ordered set.

###### Proof.

The reflexivity and symmetry of $\sim$ is obvious. To check the transitivity,
assume $(a_{n})\sim(b_{n})$ and $(b_{n})\sim(c_{n})$. Then

$\\{n\in\mathbb{N}:a_{n}=c_{n}\\}\supset\\{n\in\mathbb{N}:a_{n}=b_{n}\\}\cap\\{n\in\mathbb{N}:b_{n}=c_{n}\\}\in\mathcal{U}\hskip
56.9055pt(\star)$

implies $(a_{n})\sim(c_{n})$, so $\sim$ is indeed an equivalence relation.
Similarly, if $(a_{n})\sim(\tilde{a}_{n})\,$, $(b_{n})\sim(\tilde{b}_{n})$ and
$\overline{(a_{n})}\leq\overline{(b_{n})}$, then

$\displaystyle\\{n\in\mathbb{N}:\tilde{a}_{n}\leq\tilde{b}_{n}\\}\supset\\{n\in\mathbb{N}:a_{n}\leq
b_{n}\\}\cap\\{n\in\mathbb{N}:a_{n}=\tilde{a}_{n}\\}\cap\\{n\in\mathbb{N}:b_{n}=\tilde{b}_{n}\\}\in\mathcal{U}$

ensures that $\overline{(\tilde{a}_{n})}\leq\overline{(\tilde{b}_{n})}$, hence
$\leq$ is independent of the choice of representatives, i.e. it is a well-
defined relation on $T^{\ast}$.

Clearly $\leq$ is reflexive, and also notice that if we replace the equalities
with inequalities in $(\star)$, we get the transitivity of $\leq$.
Furthermore,

$\\{n\in\mathbb{N}:a_{n}=b_{n}\\}\supset\\{n\in\mathbb{N}:a_{n}\leq
b_{n}\\}\cap\\{n\in\mathbb{N}:b_{n}\leq a_{n}\\}\in\mathcal{U}$

shows that $\leq$ is antisymmetric. Finally, since the sets
$\\{n\in\mathbb{N}:a_{n}\leq b_{n}\\}$ and $\\{a_{n}>b_{n}\\}$ give a disjoint
partition of $\mathbb{N}$, exactly one of them is in $\mathcal{U}$. These
properties together provide that $(T^{\ast},\leq)$ is an ordered set. ∎

###  3.3. Cantor’s property for the extension

In this section we will show that the operation ∗ always produces an ordered
set that satisfies Cantor’s property.

######  Theorem 2.

If $T$ is an ordered set then its extension $T^{\ast}$ satisfies Cantor’s
property, i.e. if $a_{k}=((a_{k})_{n})\in\mathcal{T}$ and
$b_{k}=((b_{k})_{n})\in\mathcal{T}$ $(k\in\mathbb{N})$ such that for every
$k\in\mathbb{N}$

$\overline{a_{k}}\leq\overline{a_{k+1}}\leq\overline{b_{k+1}}\leq\overline{b_{k}}\,,$

then

$\bigcap_{k\in\mathbb{N}}\left[\overline{a_{k}}\,,\,\overline{b_{k}}\right]\neq\emptyset\,.$

###### Proof.

We define the following sets:

$\displaystyle A_{i}=\\{n\in\mathbb{N}:(a_{i})_{n}\leq(a_{i+1})_{n}\\},\hskip
28.45274ptB_{i}=\\{n\in\mathbb{N}:(b_{i})_{n}\geq(b_{i+1})_{n}\\},$
$\displaystyle\mbox{ and
}C_{i}=\\{n\in\mathbb{N}:(a_{i})_{n}\leq(b_{i})_{n}\\}\hskip
14.22636pt\mbox{for every }i\in\mathbb{N}.$

Using these we construct the following sets:

$\mathcal{A}_{k}=\bigcap_{i=1}^{k-1}A_{i},\mbox{\hskip 28.45274pt
}\mathcal{B}_{k}=\bigcap_{i=1}^{k-1}B_{i},\mbox{\hskip 28.45274pt
}\mathcal{C}_{k}=\bigcap_{i=1}^{k}C_{i}\mbox{\hskip
28.45274pt}(k\in\mathbb{N}\setminus\\{1\\}).$

Obviously $\mathcal{A}_{k}$, $\mathcal{B}_{k}$, $\mathcal{C}_{k}$ belong to
$\mathcal{U}$, as they are intersections of finitely many sets from
$\mathcal{U}$. For the same reason
$\mathcal{A}_{k}\cap\mathcal{B}_{k}\cap\mathcal{C}_{k}=\mathcal{D}_{k}\in\mathcal{U}$.

Let $\mathcal{D}_{1}=\mathcal{C}_{1}=C_{1}\,$, thus the set $\mathcal{D}_{k}$
is now defined for every $k\in\mathbb{N}$, and it consists of the natural
numbers $n$ for which the following inequalities hold:

$(a_{1})_{n}\leq\ldots\leq(a_{k})_{n}\leq(b_{k})_{n}\leq\ldots\leq(b_{1})_{n}.$

In the next step, for every $n\in\mathbb{N}\,$, we define another set of
natural numbers $I_{n}$ as follows:
$I_{n}=\\{k\in\mathbb{N}:n\in\mathcal{D}_{k}\\}$. It is easy to see from the
definition of the sets $\mathcal{D}_{k}$ that if $k\in I_{n}$ then $l\in
I_{n}$ is also true for every natural number $l\leq k$. Using these sets we
assign a non-negative integer to every $n\in\mathbb{N}$ as follows: let

$\alpha_{n}=\begin{cases}0,&\text{if }I_{n}=\emptyset\,,\\\ n,&\text{if
}I_{n}\text{ has no upper bound},\\\ \min\\{n,\max I_{n}\\}&\text{if
}I_{n}\text{ is non-empty and bounded from above.}\end{cases}$

We should note that if $n$ is an element of $\mathcal{D}_{k}$ and $k\leq n$
then $\alpha_{n}\geq k$ ($k,n\in\mathbb{N}$ ). This also means that
$n\notin\mathcal{D}_{1}$ holds if and only if $I_{n}=\emptyset$. Hence
$n\in\mathcal{D}_{k}\setminus\\{m\in\mathbb{N}:m<k\\}$ implies

$(a_{1})_{n}\leq\ldots\leq(a_{k})_{n}\leq(a_{\alpha_{n}})_{n}\leq(b_{\alpha_{n}})_{n}\leq(b_{k})_{n}\leq\ldots\leq(b_{1})_{n}.$

It is trivial that $\mathcal{D}_{k}\setminus\\{m\in\mathbb{N}:m<k\\}$ is in
the ultrafilter.

After these remarks it is rather easy to construct a common point of the
interval chain. We define the sequence
$c=(c_{n}):\mathbb{N}\longrightarrow\mathbb{R}$ as follows:

$c_{n}=\begin{cases}(a_{\alpha_{n}})_{n},&\text{if }n\in\mathcal{D}_{1}\\\
(a_{1})_{1},&\text{if }n\notin\mathcal{D}_{1}.\end{cases}$

We will show that $\overline{a_{k}}\leq\overline{c}\leq\overline{b_{k}}$ for
any $k\in\mathbb{N}$. This is a straightforward corollary of our previous
remark, namely that

$(a_{1})_{n}\leq\ldots\leq(a_{k})_{n}\leq(a_{\alpha_{n}})_{n}=c_{n}\leq(b_{k})_{n}\leq\ldots\leq(b_{1})_{n}$

holds if $n\in\mathcal{D}_{k}\setminus\\{m\in\mathbb{N}:m<k\\}$. Since
$\mathcal{D}_{k}\setminus\\{m\in\mathbb{N}:m<k\\}\in\mathcal{U}$, the sets

$\\{n\in\mathbb{N}:(a_{k})_{n}\leq c_{n}\\}\ \mbox{ and }\
\\{n\in\mathbb{N}:c_{n}\leq(b_{k})_{n}\\}$

are also elements of $\mathcal{U}$ (obviously they are supersets of
$\mathcal{D}_{k}\setminus\\{m\in\mathbb{N}:m<k\\}$).

The final step of the proof is to use the definition of the ordering relation
on $T^{\ast}$, so we obtain

$\overline{c}\in\bigcap_{k\in\mathbb{N}}[\overline{a_{k}},\overline{b_{k}}]$

∎

######  Remark 2.

It seems reasonable to make a similar proposition and replace the closed
intervals by open intervals. However if we do so then we must require the $T$
ordered set to be dense everywhere. Otherwise a trivial counterexample can be
made as an empty open interval exists.

On the other hand, the criterion concerning the density of $T$ is sufficient
to prove the alternate form of the previous theorem (i.e. open completeness).
We sum up these perceptions in the following theorem:

######  Theorem 3.

Let $T$ be an ordered set. The following statements are equivalent:

  * (a)

$T$ is dense everywhere.

  * (b)

if $a_{k}=((a_{k})_{n})\in\mathcal{T}$ and $b_{k}=((b_{k})_{n})\in\mathcal{T}$
$(k\in\mathbb{N})$ such that for every $k\in\mathbb{N}$

$\overline{a_{k}}\leq\overline{a_{k+1}}<\overline{b_{k+1}}\leq\overline{b_{k}}\,,$

then

$\bigcap_{k\in\mathbb{N}}\left]\overline{a_{k}}\,,\,\overline{b_{k}}\right[\neq\emptyset\,.$

###### Proof.

To show (b) $\Longrightarrow$ (a) we explain the counterexample which was
mentioned in Remark 2. Let $p,q\in T$ such that $p<q$ and there is no element
of $T$ in the open interval $]p,q[$.

This means that the open interval $\left]\overline{p},\overline{q}\right[$ is
also empty, where $\overline{p}$ and $\overline{q}$ are the classes of the
constant sequences $(p_{n})$ and $(q_{n})$ defined by $p_{n}=p$ and $q_{n}=q$
for every $n\in\mathbb{N}\,$.

Thus if $p_{k}=(p_{n})\in\mathcal{T}$ and $q_{k}=(q_{n})\in\mathcal{T}$ for
every $k\in\mathbb{N}$, then

$\bigcap_{k\in\mathbb{N}}\left]\overline{p_{k}}\,,\,\overline{q_{k}}\right[=\left]\overline{p},\overline{q}\right[=\emptyset\,.$

To show the reverse implication, we can take the same process as we did in the
proof of Theorem 2. The only adjustments to be made are that we define

$C_{i}=\\{\,n\in\mathbb{N}\,:\,(a_{i})_{n}<(b_{i})_{n}\,\\}\quad(i\in\mathbb{N})$

and $c_{n}$ has to be an element from the interior of the ’$\alpha_{n}$-th’
interval (obviously, it cannot be an endpoint as it initially was), that is,

$c_{n}\in\left](a_{\alpha_{n}})_{n}\,,\,(b_{\alpha_{n}})_{n}\right[\ \
\mbox{if}\ \ n\in\mathcal{D}_{1}\,,\ \ \mbox{while}\ \ c_{n}=(a_{1})_{1}\ \
\text{if}\ \ n\notin\mathcal{D}_{1}\,.$

Clearly, the required element $c_{n}$ exists as $T$ is dense everywhere. We
will not repeat the entire proof since every remaining step is analogous. ∎

###  3.4. Completeness of the extension

Finally we will show that the operation ∗ does not preserve completeness in
general. Moreover the completeness of the ultrapower depends only on the
cardinality of the initial ordered set.

######  Lemma 1.

Let $\mathcal{U}$ be an ultrafilter on $\mathbb{N}$ and
$A_{j}\subset\mathbb{N}$ $\ (j=1,\dots,n)$. If

$\bigcup_{j=1}^{n}A_{j}=\mathbb{N}\,\text{, then }\exists
k\in\\{1,\dots,n\\}\text{ such that }A_{k}\in\mathcal{U}$

###### Proof.

Assume that for all indices $j\in\\{1,\dots,n\\}:A_{j}\notin\mathcal{U}$. From
the definition of $\mathcal{U}$ we get $\mathbb{N}\setminus
A_{j}\in\mathcal{U}$ for every $j\in\\{1,\dots,n\\}$. This means

$\emptyset=\mathbb{N}\setminus\mathbb{N}=\mathbb{N}\setminus\bigcup_{j=1}^{n}A_{j}=\bigcap_{j=1}^{n}\left(\mathbb{N}\setminus
A_{j}\right)\in\mathcal{U}$

which is an obvious contradiction as $\emptyset$ is not infinite. Therefore
some $k\in\\{1,\dots,n\\}$ must exist for which $A_{k}\in\mathcal{U}$. ∎

######  Theorem 4.

Let $T$ be an ordered set. $T^{\ast}$ is complete if and only if $T$ is
finite.

###### Proof.

In the first place we prove that if $T$ is infinite then $T^{\ast}$ is not
complete. We will use the following basic fact: in an infinite ordered set
there exists a strictly monotone sequence of elements. In order to prove this,
we may consider an obviously existing injective sequence
$(x_{n})\colon\mathbb{N}\rightarrow T$ (i.e., $x_{n}\neq x_{m}$ if $n\neq m$).
It is a well-known fact that every sequence in an ordered set contains a
monotone subsequence (we can apply the proof for real sequences [5] in this
more general context as well). Clearly, such a monotone subsequence of
$(x_{n})$ is strictly monotone.

We give the details of the proof only for the case of a strictly increasing
sequence.

Let $t_{1}<t_{2}<t_{3}<\dots$ be a strictly increasing sequence of elements in
$T$. It is easy to see that the equivalence classes of the constant sequences

$(s_{k})_{n}=t_{k}\qquad(n\in\mathbb{N})\ (k\in\mathbb{N})$

generate a subset

$S=\\{\,\overline{s_{k}}\,\mid\,k\in\mathbb{N}\,\\}$

of $T^{\ast}$ which is bounded from above. Indeed, one can easily check that
$\overline{(t_{n})}$ is an upper bound of $S\,$. Now we demonstrate that $S$
has no least upper bound. Let $(b_{n})\in\mathcal{T}$ such that
$\overline{(b_{n})}$ is an upper bound of $S\,$. We define some sets in a
similar manner as we did in the proof of Theorem 2: let

$\mathcal{D}_{k}=\\{n\in\mathbb{N}\ :\ b_{n}\geq t_{k}\\}\in\mathcal{U},\qquad
I_{n}=\\{k\in\mathbb{N}\ :\ b_{n}\geq t_{k}\\}\qquad(k,n\in\mathbb{N}).$

We should note that if $k\in I_{n}$ then $l\in I_{n}$ for every natural number
$l\leq k$. Another easy observation is that, for any $m,k\in\mathbb{N}\,$,
$m\in\mathcal{D}_{k}$ if and only if $k\in I_{m}\,$. (we will use these two
remarks later on).

Now we can define a mapping
$\alpha:\mathbb{N}\rightarrow\mathbb{N}\cup\\{0\\}$ as follows: let

$\alpha_{n}=\begin{cases}0,&\text{if }I_{n}=\emptyset\,,\\\ n,&\text{if
}I_{n}\text{ has no upper bound},\\\ \min\\{n,\max
I_{n}\\},&\text{otherwise}.\end{cases}$

With the notation
$\beta_{n}=\left\lfloor\displaystyle\frac{\alpha_{n}}{2}\right\rfloor$ it is
possible to construct an upper bound for $S$ which is smaller than
$\overline{b}$ (here $\lfloor\ \rfloor$ denotes the floor, i.e., $\lfloor
x\rfloor=\max\\{\,z\in\mathbb{Z}\,:\,z\leq x\,\\}$).

We define $(c_{n})\in\mathcal{T}$ as follows:

$c_{n}=\begin{cases}b_{n},&\text{if }\alpha_{n}<2\\\ t_{\beta_{n}},&\text{if
}\alpha_{n}\geq 2\end{cases}$

For any natural number $k$ the following argumentation can be made: if
$\alpha_{n}\geq 2k$ then $\beta_{n}\geq k$ and therefore $c_{n}\geq t_{k}$.
Since

$\\{n\in\mathbb{N}\ :\ c_{n}\geq t_{k}\\}\supset\\{n\in\mathbb{N}\ :\
\alpha_{n}\geq 2k\\}=\mathcal{D}_{2k}\setminus\\{m\in\mathbb{N}\ :\
m<2k\\}\in\mathcal{U}$

follows from the two simple remarks that were stated earlier, we have obtained
that $\overline{(c_{n})}$ is an upper bound of $S$. On the other hand, for
every $m\in\mathcal{D}_{2}\setminus\\{1\\}\,$, the value $c_{m}$ is indeed
smaller than $b_{m}$, because $2\leq{\alpha}_{m}\in I_{m}\,$, and thus

$c_{m}=t_{\beta_{m}}<t_{\alpha_{m}}\leq b_{m},$

so $\overline{(c_{n})}<\overline{(b_{n})}$. Therefore $S$ has no least upper
bound.

With some obvious adjustments it can be shown that if
$u_{1}>u_{2}>u_{3}>\dots$ is a strictly decreasing sequence of elements in $T$
and $v_{k}\in\mathcal{T}$ such that $(v_{k})_{n}=u_{k}$ for all
$n,k\in\mathbb{N}\,$, then the set

$V=\\{\ \overline{v_{k}}\,\mid\,k\in\mathbb{N}\,\\}\subset T^{\ast}$

does not have a greatest lower bound.

In the second part of the proof we will verify the reverse implication, namely
that if $T$ is finite then $T^{\ast}$ is complete. Since a finite ordered set
is always complete, it is sufficient to show that, for any finite ordered set
$T\,$, $T^{\ast}$ is finite as well.

Let $k\in\mathbb{N}\,$, $T=\\{\,t_{1}\,,\,\dots\,,\,t_{k}\,\\}$, and for each
$j\in\\{1,\dots,k\\}$, let $s_{j}\in\mathcal{T}$ such that $(s_{j})_{n}=t_{j}$
for all $n\in\mathbb{N}$ (a constant sequence). Now let us consider an
arbitrary sequence $(a_{n})\in\mathcal{T}\,$. For every $j\in\\{1,\dots,k\\}$
we define the sets $A_{j}=\\{\,n\in\mathbb{N}\,:\,a_{n}=t_{j}\,\\}$.
Obviously, $\bigcup_{j=1}^{k}A_{j}=\mathbb{N}\,$. According to Lemma 1, there
exists an index $m\in\\{1,\dots,k\\}$ such that $A_{m}\in\mathcal{U}$ and
therefore $\overline{(a_{n})}=\overline{s_{m}}$ (i.e., $(a_{n})$ is the
equivalent with the constant $t_{m}$ sequence). So we may conclude that
$T^{\ast}$ contains only the equivalence classes of finitely many constant
sequences, which implies that $T^{\ast}$ is complete as well. ∎

## References

  * [1] Z. Boros, Á. Száz, Infimum and supremum completeness properties of ordered sets without axioms, An. Ştiinţ. Univ. "Ovidius” Constanţa Ser. Mat. 16/2 (2008), 31–37.
  * [2] P. Corazza. Revisiting the Construction of the Real Line, International Mathematical Forum 11/2 (2016), 71–94. http://dx.doi.org/10.12988/imf.2016.512104
  * [3] T. Jech, Set Theory, Springer-Verlag, Berlin – Heidelberg, 2003.
  * [4] W. A. Luxemburg, What Is Nonstandard Analysis?, Amer. Math. Monthly 80/6 (1973), 38–67.
  * [5] D. J. Newman, T. D. Parsons, On monotone subsequences, Amer. Math. Monthly 95/1 (1988), 44–45.
  * [6] K. D. Stroyan, W. A. J. Luxemburg, Introduction to the theory of infinitesimals, Academic Press, New York – San Francisco – London, 1976.