notesum.ai

Published at November 6

Rescheduling after vehicle failures in the multi-depot rural postman problem with rechargeable and reusable vehicles

cs.RO

cs.CC

cs.MA

Released Date: November 6, 2024

Authors: Eashwar Sathyamurthy¹, Jeffrey W. Herrmann¹, Shapour Azarm¹

Aff.: ¹Not specified

Arxiv: http://arxiv.org/abs/2411.04073v1

Refer to caption

Failure Scenarios created from gdb instances

Gurobi

optimal

results

Gurobi Offline Results

with vehicle failures

known beforehand

SA

Offline

Results

Centralized Auction Algorithm

for handling dynamic

vehicle failure

Failure

Scenario

Name

|N|

|E|

|E_{u}|

C

R_{T}

K

|N_{d}|

|F|

\beta_{OPT}

ET

(sec)

\beta_{OPT_{f}}

%

\Delta\beta_{OPT_{f}}

ET

(sec)

\beta_{SA}

ET

(sec)

\beta_{CA}

%

\Delta\beta_{CA}

\rho

Total

ET (sec)

gdb.1

11

19

5

40

80

2

3

1

148

133.63

251

69.59

60

148

0.01

364

145.95

1.45

60.01

gdb.2

7

21

8

16

32

4

2

1

15

4.51

16

6.67

50

15

0.00

60

300.00

3.75

50.00

gdb.3

7

21

8

12

24

4

2

1

7

1.62

8

14.29

48

7

0.00

36

414.29

4.50

48.00

gdb.4

7

21

8

12

24

4

2

2

7

1.02

8

14.29

48

7

0.00

38

442.86

4.75

48.00

gdb.5

7

21

8

12

24

4

2

3

7

0.95

10

42.86

48

7

0.00

98

1300.00

9.80

48.00

gdb.6

12

22

7

40

80

3

3

1

126

391.64

145

15.08

33

126

0.00

145

15.08

1.00

33.00

gdb.7

12

22

8

40

80

4

3

1

134

5099.18

144

7.46

45

134

0.00

146

8.96

1.01

45.00

gdb.8

12

22

8

40

80

4

3

1

34

5168.17

129

279.41

53

34

0.02

139

308.82

1.08

53.02

gdb.9

12

22

7

44

88

3

3

2

41

135.30

266

548.78

53

41

0.01

296

621.95

1.11

53.01

gdb.10

12

22

8

40

80

4

3

2

134

4842.24

240

79.10

45

134

0.01

269

100.75

1.12

45.01

gdb.11

12

22

7

44

88

3

3

1

41

259.10

146

256.10

53

41

0.00

167

307.32

1.14

53.00

gdb.12

11

22

8

18

36

4

3

2

16

213.22

63

293.75

71

16

0.00

103

543.75

1.63

71.00

gdb.13

12

22

7

40

80

3

3

2

126

125.51

154

22.22

33

126

0.00

265

110.32

1.72

33.00

gdb.14

11

22

8

18

36

4

3

1

16

39.48

17

6.25

71

16

0.00

65

306.25

3.82

71.00

gdb.15

13

23

7

60

120

3

3

1

59

716.11

221

274.58

58

59

0.00

238

303.39

1.08

58.00

gdb.16

12

25

9

38

76

4

3

1

120

15905.67

121

0.83

62

120

0.00

149

24.17

1.23

62.00

gdb.17

12

25

9

38

76

4

3

3

120

824.66

352

193.33

62

120

0.00

541

350.83

1.54

62.00

gdb.18

12

25

9

38

76

4

3

2

120

4332.88

134

11.67

62

120

0.00

233

94.17

1.74

62.00

gdb.19

12

26

9

40

80

4

3

1

40

11492.90

141

252.50

64

40

0.00

231

477.50

1.64

64.00

gdb.20

13

26

7

44

88

3

3

1

141

5206.36

141

0.00

73

141

0.00

267

89.36

1.89

73.00

gdb.21

8

28

10

16

32

5

2

1

12

26.91

13

8.33

71

12

0.00

53

341.67

4.08

71.00

gdb.22

8

28

10

14

28

5

2

2

10

23.58

11

10.00

67

10

0.00

47

370.00

4.27

67.00

gdb.23

8

28

10

14

28

5

2

1

10

2.65

10

0.00

67

10

0.00

45

350.00

4.50

67.00

gdb.24

8

28

10

16

32

5

2

2

12

67.94

14

16.67

71

12

0.00

90

650.00

6.43

71.00

gdb.25

10

28

9

198

396

4

3

2

48

46.21

58

20.83

81

48

0.00

490

920.83

8.45

81.00

gdb.26

10

28

9

198

396

4

3

1

48

22.63

48

0.00

81

48

0.01

485

910.42

10.10

81.01

gdb.27

11

33

11

18

36

5

3

3

15

1829.71

60

300.00

83

15

0.01

114

660.00

1.90

83.01

gdb.28

11

33

11

18

36

5

3

1

15

601.29

15

0.00

83

15

0.00

63

320.00

4.20

83.00

gdb.29

11

33

11

18

36

5

3

2

15

167.81

15

0.00

83

15

0.00

65

333.33

4.33

83.00

gdb.30

9

36

13

16

32

6

2

3

13

35622.56

52

300.00

94

13

0.00

57

338.46

1.10

94.00

gdb.31

9

36

13

16

32

6

2

2

13

58.43

16

23.08

94

13

0.00

56

330.77

3.50

94.00

gdb.32

9

36

13

16

32

6

2

1

13

1406.40

13

0.00

94

13

0.00

54

315.38

4.15

94.00

gdb.33

11

44

14

18

36

7

3

5

11

1108.67

60

445.45

97

11

0.00

149

1254.55

2.48

97.00

gdb.34

11

44

14

18

36

7

3

3

11

8509.65

14

27.27

97

11

0.00

57

418.18

4.07

97.00

gdb.35

11

44

14

18

36

7

3

1

11

21451.41

13

18.18

97

11

0.00

57

418.18

4.38

97.00

gdb.36

11

44

14

18

36

7

3

2

11

22016.09

13

18.18

97

11

0.00

58

427.27

4.46

97.00

gdb.37

11

44

14

18

36

7

3

4

11

1777.33

15

36.36

97

11

0.00

103

836.36

6.87

97.00