Problem Setting

Overview

• Concept: In this programming contest, you will run a delivery service. Customers will place orders with your shop. Each order has a unique $\\text{ID}$ and should be delivered to the corresponding customer. Your delivery service has one car. The car will fetch the ordered item from the shop and deliver it to the customer.
• Score: Your goal is to deliver as many items as possible, as quickly as possible in a given amount of time $T_{\\text{max}}$. (Orders are expected until $0.95 \\times T_{\\text{max}}$).
• Constraint: In this contest there is no constraint on the number of items you can place in the car. However, an item can only be loaded in the car, by fetching it from the shop, after the order has been placed.
• Problem A/B: In problem A all order positions and times are given to the contestant in advance and the contestant algorithm shall optimize the moves of the car to make as many deliveries as possible as fast as possible. On the other hand, in problem B orders appear online, that is new orders appear, while you move your car to make as many deliveries as possible as fast as possible.

Specification of Time and Space:

• Time: In this contest we model the progress of time by integer values $0 \\le t < T_{\\text{max}}$.
• Map: In this contest we model a map by a simple, undirected, and connected graph $G=(V, E)$, consisting of a set of vertices $V$ and a set of edges $E$
• Shop and customer locations: The vertices $u \\in V$ are labeled from $1$ to $|V|$ and the vertex $u=1$ denotes the location of your shop, while vertices $u = 2,...,|V|$ denote locations of potential customers. Here, $|V|$ denotes the number of elements of the set $V$.
• Streets: Each edge $\\left\\{ u, v \\right\\} \\in E$ represents a street connecting the vertices $u, v \\in V$. The corresponding length is given by an integer edge weight $d_{u, v} \\ge 1$.
• Graph creation: The algorithm for generating the map graph based on a random seed is specified in the following pseudo-code. For further details, please see the sample code below.

Pseudo code: Map graph generator

• Input:$|V|$, $|E|$, $\\mathrm{MaxDegree}=5$
• 2d vertex grid:
  • First, find the largest integer $R>0$ such that $|V| = R^{2} + r$, with $r$ being the smallest possible non-negative integer.
  • Then we plot points $(x, y)$ on the 2d vertex grid $(0 \\leq x, y \\lt R)$.
  • For each point $(x, y)$ add a uniform random offset dx, dy \\in \[0, 1\] , giving the final vertex position (x + dx, y + dy)\\in \[0,R\] \\times \[0,R\].
  • Finally, add the remaining $r$ vertices at a uniform random position $(x, y)$ with $0 \\leq x, y \\leq R$.
  • Vertex labels $u \\in V$ are assigned by random shuffling. The shop is the vertex $u=1$.
• How we create Highways:
  • To generate a highway network, we create a complete graph $G_{\\text{comp}}$ on the vertex set $u \\in V$, assigning each vertex pair $u, v \\in V \\times V$ the Euclidean distance $W_{u, v}$ as an edge weight.
  • Next, we construct a minimum spanning tree of $G_{\\text{comp}}$. The $|V|-1$ edges of the minimum spanning tree are the highway network of the graph $G$. We assign each of those edges $\\left\\{ u, v \\right\\}$ an edge weight $d_{u,v} \\leftarrow \\lceil 2 \\times W_{u, v} \\rceil$ .
• How we add side roads:
  • To create a network of side roads, we successively add $|E|-(|V|-1)$ edges to the graph $G$ as follows:
    • Update $\\mathrm{cost}(u,v)$.
    • Among the vertex pairs $\\left( u, v \\right) \\in V\\times V$, not yet connected by an edge, select a pair with minimal $\\mathrm{cost}(u,v)$.
    • Assign the edge weight $d_{u,v} \\leftarrow \\lceil 4 \\times W_{u, v} \\rceil$ .
  • Here, $\\mathrm{cost}(u,v)$ is essentially based on the Euclidean distance of vertices, giving preference to connecting nearby vertices with low degree. In addition, preference is given to side roads along the rectangular grid, to avoid too many bridges. The detailed definitions are as follows:
    • Define $\\mathrm{degree}(u)$, the degree of vertex $u\\in V$ as the number of incident edges.
    • Define $\\mathrm{color}(u)$ for each vertex $u\\in V$ according to its original position $(x,y)$ on the vertex grid as:
      • If $x+y$ is even : $\\mathrm{color}(u) = 0$
      • If $x+y$ is odd : $\\mathrm{color}(u) = 1$
      • For the remaining $r$ vertices : Assign a color $\\mathrm{color}(u) \\in \\left\\{0,1\\right\\}$ at random.
    • Define a factor $f(u,v)$ as follows:
      • If $\\mathrm{color}(u)$ and $\\mathrm{color}(v)$ are the same : Set $\\mathrm{f}(u,v) = 5$
      • If $\\mathrm{color}(u)$ and $\\mathrm{color}(v)$ are different : Set $\\mathrm{f}(u,v) = 1$
    • Define a factor $g(u)$ as follows:
      • If $\\mathrm{degree}(u) \\lt \\mathrm{MaxDegree}$ : Set $g(u)=1$
      • If $\\mathrm{degree}(u) \\geq \\mathrm{MaxDegree}$ : Set $g(u)=\\infty$
    • Finally, the cost is defined as follows:
      • $\\mathrm{cost}(u,v) = W_{u,v}\\times \\mathrm{degree}(u) \\times \\mathrm{degree}(v) \\times f(u,v) \\times g(u) \\times g(v)$.
• How we assign order frequencies:
  • Assign each vertex $u \\in V$ an order frequency $f_u \\in \\left\\{0,1,2\\right\\}$.
  • Init the order frequency of the shop vertex: $f_1 \\leftarrow 0$.
  • Init the order frequency of the other vertices: $f_u \\leftarrow 1$
  • Now determine vertices with order frequency 2. For this draw a uniform random center point c=(c_x,c_y)\\in \[R/4,3R/4\]\\times\[R/4,3R/4\] and then for all vertices $u=2,...,|V|$ do:
    • If $\\mathrm{EuclideanDistance}(c,u)\\le R/8 + \\mathrm{uniformRandom}\[0,R/8\]$: $f_{u} \\leftarrow 2$

Specification of Car Locations and Moves:

In order to make deliveries you will operate a delivery car, which can take positions and make moves as specified below.

• Car position: A car can generally take two types of position:

  • on a vertex $u \\in V$.
  • on an edge $\\left\\{ u, v \\right\\} \\in E$. More specifically, it is located at a distance $x$ $(0 \\lt x \\lt d_{u, v})$ from $u$ to $v$ .

• Car move: At each step $0 \\le t < T_{\\text{max}}$ you have to choose one of the following actions in order to control your delivery car.

  • stay: stay at the current position.
  • move w: Take one step towards vertex $w \\in V$.

  In case of choosing move w, $w$ must obey the following constraints. A failure to obey these constraints results in a wrong answer WA.

  • $w$ must be a vertex, i.e., $w \\in V$.
  • If the car is on vertex $u \\in V$, there must be an edge connecting $u$ and $v$, i.e., $\\left\\{ u, w \\right\\} \\in E$.
  • If the car is on the edge $\\left\\{ u, v \\right\\} \\in E$, $w$ must either be $w = u$ or $w = v$.

Orders, Deliveries, and Constraints:

• Orders: Throughout the contest each order is characterized by three quantities: A unique order ID, a vertex $v \\in V$ indicating the order destination, and the order time $t$ at which the order appeared. For the detailed format see below.
• Order generation: At each time $0 \\le t \\le T_{\\text{last}} = 0.95 \\times T_{\\text{max}}$ up to one new order can appear with probability $p_{\\text{order}}(t)$. In case there is an order, the order destination $i$ is chosen from the vertex set $V$ with probability proportional to the order frequency $f_i$. For details, see the pseudo-code below or the sample code further below.

Pseudo code: Order generation

• Input: Last order time $T_{\\text{last}}$ and average order probability $p_{\\text{order}}(t)$.

• Init: $\\mathrm{ID} \\leftarrow 0$.

• For each step $t = 0, ..., T_{\\text{last}}$ do:

  • Generate a uniform random number r \\in \[0,1\] .
  • If $r \\le p_{\\text{order}}(t)$ :
    • Select a vertex position $u \\in V$ at random with probability proportional to the order frequency $f_{u}$ of the vertex.
    • $\\mathrm{ID} \\leftarrow \\mathrm{ID} + 1$
    • place order (new order ID, order time $t$, vertex position $u \\in V$ )
  • Else: place no order

• Note: The average order probability is defined as follows:

• $p_{\\text{order}}(t) = \\begin{cases} t / T_{\\text{peak}}, & \\text{if } 0\\le t \\lt T_{\\text{peak}}, \\\\ (T_{\\text{last}} - t) / (T_{\\text{last}}- T_{\\text{peak}}), & \\text{if } T_{\\text{peak}} \\le t \\lt T_{\\text{last}}, \\\\ 0, & \\text{if } T_{\\text{last}} \\le t, \\end{cases}$

• where $T_{\\text{last}}:=0.95 \\times T_{\\max}$ and $T_{\\text{peak}}$ is drawn randomly uniform from the interval \[0, T_{\\text{last}}\].

• Note: The value of $T_{\\text{peak}}$ will not be given as an input.

• Delivery: To deliver an order, the contestant must do the following steps after the order has been placed:
  • (1st) Move the car onto the shop: Note: When moving a car onto the shop, all orders with order time less than or equal to the current time, will be transfered into the car. On the other hand, orders which have not appeared yet, cannot be placed into the car.
  • (2nd) Move the car to the customer position: To finalize a delivery, move the car onto the vertex of the customer position. Note: Orders which have not been transfered into the car yet, will not be delivered, even if you arrive at the customer position.

• Constraints: Throughout the contest, we assume each order has a unique $\\text{ID}$ and should be delivered to the corresponding customer. It is further assumed that an unlimited number of orders can be placed in the car.

Scoring

• During the contest the total score of a submission is determined by summing the score of the submission with respect to 30 input cases.

• After the contest a system test will be performed. To this end, the contestant's last submission will be scored by summing the score of the submission on 100 previously unseen input cases.

• For each input case, the score is calculated as follows:

  $\\text{Score} = \\sum_{i \\in D} {(T_{\\text{max}})}^{2} - {(\\mathrm{waitingTime}_i)}^{2},$

  Here we use the following definitions:

  • $D$ : the set of orders delivered until $t=T_{\\text{max}}$
  • the waiting time of the $i$th order: $\\mathrm{waitingTime}_i = \\mathrm{deliveredTime}_i - \\mathrm{orderedTime}_i$.
  • Note that an input case giving the output WA will receive $0$ points.

Particulars of Problem B:

Problem B is an interactive