Uncertain Capacitated Arc Routing Problem with Time Window

A CARP instance is defined on a connected graph $G=(V,E)$, in which $V$ represents a set of vertices and $E$ represents a set of edges. There is a $depot\in V$ and all vehicles must start and end at $depot$. Subset $T\in E$ is the set of all the edges required to be served, called task set. Each required edge $e\in T$ is associated with a demand $d$ ($d\geq 0$), which has to be served by one and only one pre-define vehicle. Each edge $e\in E$ is associated with a cost $c$ that a vehicle takes to traverse.

A set of CARP instances can be used to approximate the Uncertain Capacitated Routing Problem (UCARP). Let $\theta$ be a UCARP instance where $\theta$ = {$I_{1}$, $I_{2}$, …, $I_{N}$}. For any $j\in\{1,...,N\}$, $I_{j}$ is a CARP instance. All $I_{j}\in\theta$ are related but different from each other. $UT$ is the union set of task set of each CARP instances in $\theta$, i.e., $UT=\cup_{j=1}^{N}T_{j},\forall j\in\{1,...,N\}$ and $T_{j}$ is the instance of $I_{j}$ [wang2015estimation]

Comparing with UCARP, UCARP-TW needs some additional restrictions. A soft time window [$a$,$b$] is added on every required task.

Considering that the UCARP-TW data set we use is created through adding uncertainty to a CARP-TW data set, there may be no solution for the new problem if we add hard window to original task, which means every task should be served in a special interval. For example, there may be a task can not be served in time even we set it as the first task of the first route in the solution because of the changes in the edges.

Therefore, we choose to add a soft window, which is much more flexible and close to the real life. Comparing with using hard time window, using soft window would add a penalty to the total cost of this road, rather than force each task to be served in its time window.

We set s=($R_{1}$,$R_{2}$,…,$R_{m}$) as a solution of the UCARP-TW, where $R_{k}$=($t_{k,1}$,…,$t_{k,l_{k}}$)[wang2015estimation]. $R_{k}$ is the k-th route. $l_{k}$ is the length of the k-th route and $t_{k,b}$ is the b-th task served in the k-th route. Let head(t) and tail(t) be the two endpoints of task t, inv(t) is task t with inverse direction. Q is the capacity of a vehicle.[wang2015estimation] $d(t,I_{j})$ is the demand of task t in instance $I_{j}$.

UCARP-TW can be formulated as

To verify our algorithm, we construct a new UCARP-TW dataset, which is based on CARP-TW instances and generated by the instance generator for UCARP[wang2015estimation]. One UCARP-TW instance contains 30 CARP-TW instances sharing the same graph structure. It is worth noting that only the cost and demand of edges are uncertain but there is no uncertainty on time window of edges, that is to say the time window on the same edge are the same in one UCARP-TW instance.

The parameters for EDASLS in UCARP-TW algorithm is shown in Table LABEL:param, other parameters for the following experiments are listed below in Table II. (processor and processor of original paper)

First, 20 independent runs are performed on every instance of UCARP-TW and the average execution time, average fitness and standard deviation of fitness are calculated. To compare the result with UCARP without time window, we remove the time windows in CARP-TW and generate a set of UCARP instances with the same graph structure as UCARP-TW and compare the fitness, as shown below in Table III. Besides, to compare our result with tabu search algorithm[lai2020split], the average cost of 10 runs of the tabu search algorithm is also listed. It is worth noting that tabu search result is obtained from CARP-TW instances and the returned results satisfy the time window constraints.

As shown in the above table, we can first estimate the punishment for violating time window constraints by the difference of cost between UCARP-TW and UCARP datasets. Also, there are some instances that the corresponding cost for UCARP-TW is smaller than CARP-TW. This is because tabu search on CARP-TW will only return solutions that satisfy the time window constraint. However, as we define our problem to be constraint by soft time windows, our solution can violate the time window constraint if the penalty for violating the time window is smaller than the cost for satisfying the time constraint.