37b28e62f06141dee1e2e29dcfb99aba Bat_a2023v9n8p416.pdf e4bc4531ac9f262f111f65958e7c2ab32fb7b444 Bat_a2023v9n8p416.pdf 73e9f4d378c2d9fbafd16156745a5c8eb0c5793b099067d020e0273f41aebdb9 Bat_a2023v9n8p416.pdf Title: Using Reinforcement Learning to Solve a Dynamic Orienteering Problem with Random Rewards Affected by the Battery Status Subject: This paper discusses an orienteering optimization problem where a vehicle using electric batteries must travel from an origin depot to a destination depot while maximizing the total reward collected along its route. The vehicle must cross several consecutive regions, with each region containing different types of charging nodes. A charging node has to be selected in each region, and the reward for visiting each node—in terms of a `satisfactory' charging process—is a binary random variable that depends upon dynamic factors such as the type of charging node, weather conditions, congestion, battery status, etc. To learn how to efficiently operate in this dynamic environment, a hybrid methodology combining simulation with reinforcement learning is proposed. The reinforcement learning component is able to make informed decisions at each stage, while the simulation component is employed to validate the learning process. The computational experiments show how the proposed methodology is capable of design routing plans that are significantly better than non-informed decisions, thus allowing for an efficient management of the vehicle's battery under such dynamic conditions. Keywords: orienteering problem; battery management; electric vehicle; reinforcement learning; simulation Author: Angel A. Juan, Carolina A. Marugan, Yusef Ahsini, Rafael Fornes, Javier Panadero, Xabier A. Martin Creator: LaTeX with hyperref Producer: pdfTeX-1.40.21 CreationDate: Thu Aug 10 08:53:08 2023 CEST ModDate: Thu Aug 10 11:39:40 2023 CEST Custom Metadata: no Metadata Stream: no Tagged: no UserProperties: no Suspects: no Form: none JavaScript: no Pages: 16 Encrypted: no Page size: 595.276 x 841.89 pts (A4) Page rot: 0 File size: 2178009 bytes Optimized: no PDF version: 1.7 name type encoding emb sub uni object ID ------------------------------------ ----------------- ---------------- --- --- --- --------- HWNPXQ+URWPalladioL-Bold Type 1 Custom yes yes no 10 0 SDXHXW+URWPalladioL-Roma Type 1 Custom yes yes no 15 0 ACOZGP+URWPalladioL-Ital Type 1 Custom yes yes no 19 0 HYCPMT+TimesNewRomanPS-BoldItalicMT Type 1C WinAnsi yes yes no 38 0 GIGFZE+CMR10 Type 1 Builtin yes yes no 72 0 XWAUOZ+CMSY10 Type 1 Builtin yes yes no 76 0 QQXUPP+PazoMath Type 1 Builtin yes yes no 80 0 QGZUJO+PazoMath-Italic Type 1 Builtin yes yes no 87 0 DBOOST+URWPalladioL-BoldItal Type 1 Custom yes yes no 91 0 HXSDIM+SFTT0800 Type 1 Custom yes yes no 111 0 Jhove (Rel. 1.28.0, 2023-05-18) Date: 2024-04-20 02:36:01 CEST RepresentationInformation: Bat_a2023v9n8p416.pdf ReportingModule: PDF-hul, Rel. 1.12.4 (2023-03-16) LastModified: 2024-04-19 16:25:52 CEST Size: 2178009 Format: PDF Version: 1.7 Status: Well-Formed and valid SignatureMatches: PDF-hul MIMEtype: application/pdf PDFMetadata: Objects: 285 FreeObjects: 1 IncrementalUpdates: 0 DocumentCatalog: PageLayout: SinglePage PageMode: UseNone Outlines: Item: Title: Introduction Destination: section.1 Item: Title: Some Technical Details on EVs Destination: section.2 Item: Title: Related Work on Vehicle Orienteering Problems Destination: section.3 Item: Title: Modeling the Dynamic OP with Binary Random Rewards Destination: section.4 Item: Title: A Numerical Case Study Destination: section.5 Item: Title: Simulation and Algorithm Details Destination: section.6 Item: Title: Computational Experiments Destination: section.7 Item: Title: Conclusions Destination: section.8 Item: Title: References Destination: section.9 Info: Title: Using Reinforcement Learning to Solve a Dynamic Orienteering Problem with Random Rewards Affected by the Battery Status Author: Angel A. Juan, Carolina A. Marugan, Yusef Ahsini, Rafael Fornes, Javier Panadero, Xabier A. Martin Subject: This paper discusses an orienteering optimization problem where a vehicle using electric batteries must travel from an origin depot to a destination depot while maximizing the total reward collected along its route. The vehicle must cross several consecutive regions, with each region containing different types of charging nodes. A charging node has to be selected in each region, and the reward for visiting each node in terms of a `satisfactory' charging process is a binary random variable that depends upon dynamic factors such as the type of charging node, weather conditions, congestion, battery status, etc. To learn how to efficiently operate in this dynamic environment, a hybrid methodology combining simulation with reinforcement learning is proposed. The reinforcement learning component is able to make informed decisions at each stage, while the simulation component is employed to validate the learning process. The computational experiments show how the proposed methodology is capable of design routing plans that are significantly better than non-informed decisions, thus allowing for an efficient management of the vehicle's battery under such dynamic conditions. Keywords: orienteering problem; battery management; electric vehicle; reinforcement learning; simulation Creator: LaTeX with hyperref Producer: pdfTeX-1.40.21 CreationDate: Thu Aug 10 08:53:08 CEST 2023 ModDate: Thu Aug 10 11:39:40 CEST 2023 ID: 0x52e140c8fbbed3299aef7fd4dc6e2d1b, 0x52e140c8fbbed3299aef7fd4dc6e2d1b Filters: FilterPipeline: FlateDecode Images: Image: NisoImageMetadata: FormatName: image/png ImageWidth: 711 ImageHeight: 400 ColorSpace: RGB BitsPerSample: 8 BitsPerSampleUnit: integer Filter: FlateDecode Image: NisoImageMetadata: FormatName: image/png ImageWidth: 5600 ImageHeight: 8750 ColorSpace: RGB BitsPerSample: 8 BitsPerSampleUnit: integer Filter: FlateDecode Image: NisoImageMetadata: FormatName: image/png ImageWidth: 551 ImageHeight: 315 ColorSpace: RGB BitsPerSample: 8 BitsPerSampleUnit: integer Filter: FlateDecode Image: NisoImageMetadata: FormatName: image/png ImageWidth: 5123 ImageHeight: 2152 ColorSpace: RGB BitsPerSample: 8 BitsPerSampleUnit: integer Filter: FlateDecode Image: NisoImageMetadata: FormatName: image/png ImageWidth: 3000 ImageHeight: 1800 ColorSpace: RGB BitsPerSample: 8 BitsPerSampleUnit: integer Filter: FlateDecode Fonts: Type1: Font: BaseFont: QQXUPP+PazoMath FontSubset: true FirstChar: 229 LastChar: 229 FontDescriptor: FontName: QQXUPP+PazoMath Flags: Symbolic FontBBox: -40, -283, 878, 946 FontFile: true Font: BaseFont: ACOZGP+URWPalladioL-Ital FontSubset: true FirstChar: 40 LastChar: 122 FontDescriptor: FontName: ACOZGP+URWPalladioL-Ital Flags: Symbolic FontBBox: -170, -305, 1010, 941 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: QGZUJO+PazoMath-Italic FontSubset: true FirstChar: 35 LastChar: 115 FontDescriptor: FontName: QGZUJO+PazoMath-Italic Flags: Symbolic FontBBox: -70, -277, 902, 733 FontFile: true Font: BaseFont: GIGFZE+CMR10 FontSubset: true FirstChar: 40 LastChar: 61 FontDescriptor: FontName: GIGFZE+CMR10 Flags: Symbolic FontBBox: -40, -250, 1009, 750 FontFile: true Font: BaseFont: HWNPXQ+URWPalladioL-Bold FontSubset: true FirstChar: 3 LastChar: 121 FontDescriptor: FontName: HWNPXQ+URWPalladioL-Bold Flags: Symbolic FontBBox: -152, -301, 1000, 935 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: DBOOST+URWPalladioL-BoldItal FontSubset: true FirstChar: 105 LastChar: 107 FontDescriptor: FontName: DBOOST+URWPalladioL-BoldItal Flags: Symbolic FontBBox: -170, -300, 1073, 935 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: XWAUOZ+CMSY10 FontSubset: true FirstChar: 0 LastChar: 110 FontDescriptor: FontName: XWAUOZ+CMSY10 Flags: Symbolic FontBBox: -29, -960, 1116, 775 FontFile: true Font: BaseFont: SDXHXW+URWPalladioL-Roma FontSubset: true FirstChar: 2 LastChar: 252 FontDescriptor: FontName: SDXHXW+URWPalladioL-Roma Flags: Symbolic FontBBox: -166, -283, 1021, 943 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: HXSDIM+SFTT0800 FontSubset: true FirstChar: 33 LastChar: 125 FontDescriptor: FontName: HXSDIM+SFTT0800 Flags: Symbolic FontBBox: -213, -359, 1395, 851 FontFile: true EncodingDictionary: Differences: true Pages: Page: Sequence: 1 Annotations: Annotation: Subtype: Link Rect: 124, 281, 152, 290 Annotation: Subtype: Link Rect: 34, 269, 140, 278 Annotation: Subtype: Link Rect: 34, 164, 96, 186 Annotation: Subtype: Link Rect: 126, 90, 154, 99 Annotation: Subtype: Link Rect: 34, 78, 147, 87 Annotation: Subtype: Link Rect: 34, 756, 151, 792 Annotation: Subtype: Link Rect: 515, 756, 560, 792 Annotation: Subtype: Link Rect: 111, 642, 122, 655 Annotation: Subtype: Link Rect: 228, 642, 239, 655 Annotation: Subtype: Link Rect: 307, 642, 318, 655 Annotation: Subtype: Link Rect: 390, 642, 401, 655 Annotation: Subtype: Link Rect: 483, 642, 494, 655 Annotation: Subtype: Link Rect: 137, 631, 148, 643 Annotation: Subtype: Link Rect: 386, 221, 393, 230 ActionDest: 130 Annotation: Subtype: Link Rect: 109, 17, 259, 28 Annotation: Subtype: Link Rect: 406, 17, 560, 28 Annotation: Subtype: Link Rect: 34, 366, 87, 385 Page: Sequence: 2 Annotations: Annotation: Subtype: Link Rect: 358, 660, 365, 669 ActionDest: 130 Annotation: Subtype: Link Rect: 344, 647, 351, 657 ActionDest: 130 Annotation: Subtype: Link Rect: 278, 547, 285, 556 ActionDest: 133 Annotation: Subtype: Link Rect: 285, 547, 292, 556 ActionDest: 133 Annotation: Subtype: Link Rect: 398, 519, 404, 531 ActionDest: 57 Annotation: Subtype: Link Rect: 459, 59, 466, 69 ActionDest: 133 Page: Sequence: 3 Annotations: Annotation: Subtype: Link Rect: 451, 632, 458, 644 ActionDest: 63 Annotation: Subtype: Link Rect: 419, 595, 426, 607 ActionDest: 66 Annotation: Subtype: Link Rect: 199, 582, 206, 594 ActionDest: 69 Annotation: Subtype: Link Rect: 440, 582, 447, 594 ActionDest: 84 Annotation: Subtype: Link Rect: 331, 570, 338, 582 ActionDest: 103 Annotation: Subtype: Link Rect: 463, 557, 470, 569 ActionDest: 116 Annotation: Subtype: Link Rect: 396, 544, 403, 556 ActionDest: 123 Annotation: Subtype: Link Rect: 549, 497, 556, 506 ActionDest: 133 Annotation: Subtype: Link Rect: 393, 459, 399, 468 ActionDest: 133 Annotation: Subtype: Link Rect: 397, 434, 404, 443 ActionDest: 133 Annotation: Subtype: Link Rect: 405, 434, 417, 443 ActionDest: 133 Annotation: Subtype: Link Rect: 401, 421, 413, 430 ActionDest: 133 Annotation: Subtype: Link Rect: 314, 359, 326, 368 ActionDest: 133 Annotation: Subtype: Link Rect: 266, 296, 278, 305 ActionDest: 133 Annotation: Subtype: Link Rect: 343, 258, 355, 267 ActionDest: 133 Annotation: Subtype: Link Rect: 213, 233, 225, 242 ActionDest: 133 Annotation: Subtype: Link Rect: 452, 183, 464, 192 ActionDest: 133 Annotation: Subtype: Link Rect: 543, 170, 555, 179 ActionDest: 133 Annotation: Subtype: Link Rect: 510, 70, 522, 79 ActionDest: 133 Annotation: Subtype: Link Rect: 522, 70, 534, 79 ActionDest: 133 Page: Sequence: 4 Annotations: Annotation: Subtype: Link Rect: 423, 723, 435, 732 ActionDest: 133 Annotation: Subtype: Link Rect: 193, 710, 205, 719 ActionDest: 133 Annotation: Subtype: Link Rect: 340, 673, 352, 682 ActionDest: 133 Annotation: Subtype: Link Rect: 232, 647, 244, 657 ActionDest: 133 Annotation: Subtype: Link Rect: 481, 597, 493, 606 ActionDest: 133 Annotation: Subtype: Link Rect: 544, 560, 556, 569 ActionDest: 133 Annotation: Subtype: Link Rect: 308, 459, 320, 468 ActionDest: 133 Annotation: Subtype: Link Rect: 237, 372, 249, 380 ActionDest: 133 Annotation: Subtype: Link Rect: 461, 346, 473, 355 ActionDest: 133 Annotation: Subtype: Link Rect: 224, 309, 236, 318 ActionDest: 133 Annotation: Subtype: Link Rect: 327, 309, 339, 318 ActionDest: 133 Annotation: Subtype: Link Rect: 466, 309, 478, 318 ActionDest: 133 Annotation: Subtype: Link Rect: 487, 183, 499, 192 ActionDest: 133 Annotation: Subtype: Link Rect: 441, 133, 453, 142 ActionDest: 133 Annotation: Subtype: Link Rect: 449, 95, 456, 104 ActionDest: 130 Page: Sequence: 5 Annotations: Annotation: Subtype: Link Rect: 472, 723, 483, 732 ActionDest: 133 Annotation: Subtype: Link Rect: 544, 710, 555, 719 ActionDest: 136 Annotation: Subtype: Link Rect: 266, 698, 277, 707 ActionDest: 136 Annotation: Subtype: Link Rect: 353, 698, 364, 707 ActionDest: 136 Annotation: Subtype: Link Rect: 437, 698, 449, 707 ActionDest: 136 Annotation: Subtype: Link Rect: 477, 660, 489, 669 ActionDest: 136 Annotation: Subtype: Link Rect: 221, 647, 233, 657 ActionDest: 136 Annotation: Subtype: Link Rect: 201, 635, 212, 644 ActionDest: 136 Annotation: Subtype: Link Rect: 210, 622, 221, 631 ActionDest: 136 Annotation: Subtype: Link Rect: 342, 622, 354, 631 ActionDest: 136 Annotation: Subtype: Link Rect: 534, 622, 546, 631 ActionDest: 136 Annotation: Subtype: Link Rect: 452, 610, 463, 619 ActionDest: 136 Annotation: Subtype: Link Rect: 342, 572, 353, 581 ActionDest: 136 Annotation: Subtype: Link Rect: 246, 396, 258, 405 ActionDest: 133 Page: Sequence: 6 Annotations: Annotation: Subtype: Link Rect: 337, 733, 344, 745 ActionDest: 69 Annotation: Subtype: Link Rect: 343, 720, 350, 732 ActionDest: 69 Annotation: Subtype: Link Rect: 376, 720, 383, 732 ActionDest: 69 Annotation: Subtype: Link Rect: 513, 708, 520, 720 ActionDest: 69 Annotation: Subtype: Link Rect: 495, 683, 502, 695 ActionDest: 69 Annotation: Subtype: Link Rect: 465, 670, 472, 682 ActionDest: 69 Annotation: Subtype: Link Rect: 498, 670, 505, 682 ActionDest: 69 Annotation: Subtype: Link Rect: 266, 607, 273, 619 ActionDest: 57 Annotation: Subtype: Link Rect: 471, 582, 478, 594 ActionDest: 63 Annotation: Subtype: Link Rect: 351, 507, 358, 519 ActionDest: 84 Annotation: Subtype: Link Rect: 383, 375, 390, 387 ActionDest: 98 Annotation: Subtype: Link Rect: 374, 98, 381, 110 ActionDest: 84 Page: Sequence: 7 Annotations: Annotation: Subtype: Link Rect: 552, 319, 559, 331 ActionDest: 103 Page: Sequence: 8 Page: Sequence: 9 Annotations: Annotation: Subtype: Link Rect: 220, 470, 227, 482 ActionDest: 108 Annotation: Subtype: Link Rect: 318, 269, 325, 281 ActionDest: 108 Annotation: Subtype: Link Rect: 238, 259, 250, 268 ActionDest: 136 Annotation: Subtype: Link Rect: 249, 209, 260, 218 ActionDest: 136 Annotation: Subtype: Link Rect: 290, 184, 302, 193 ActionDest: 136 Annotation: Subtype: Link Rect: 315, 156, 322, 168 ActionDest: 108 Page: Sequence: 10 Annotations: Annotation: Subtype: Link Rect: 276, 383, 283, 395 ActionDest: 116 Annotation: Subtype: Link Rect: 494, 210, 506, 219 ActionDest: 136 Annotation: Subtype: Link Rect: 272, 182, 279, 194 ActionDest: 116 Page: Sequence: 11 Annotations: Annotation: Subtype: Link Rect: 211, 134, 218, 146 ActionDest: 120 Page: Sequence: 12 Annotations: Annotation: Subtype: Link Rect: 277, 660, 289, 669 ActionDest: 136 Annotation: Subtype: Link Rect: 357, 225, 364, 237 ActionDest: 123 Annotation: Subtype: Link Rect: 218, 100, 225, 112 ActionDest: 123 Page: Sequence: 13 Page: Sequence: 14 Annotations: Annotation: Subtype: Link Rect: 311, 560, 323, 569 ActionDest: 136 Annotation: Subtype: Link Rect: 379, 121, 416, 132 Annotation: Subtype: Link Rect: 113, 87, 151, 97 Annotation: Subtype: Link Rect: 427, 75, 465, 86 Page: Sequence: 15 Annotations: Annotation: Subtype: Link Rect: 337, 722, 374, 733 Annotation: Subtype: Link Rect: 281, 699, 318, 710 Annotation: Subtype: Link Rect: 418, 595, 456, 606 Annotation: Subtype: Link Rect: 489, 572, 527, 583 Annotation: Subtype: Link Rect: 59, 538, 96, 548 Annotation: Subtype: Link Rect: 259, 491, 296, 502 Annotation: Subtype: Link Rect: 108, 435, 146, 445 Annotation: Subtype: Link Rect: 300, 411, 337, 422 Annotation: Subtype: Link Rect: 210, 389, 248, 399 Annotation: Subtype: Link Rect: 424, 342, 462, 353 Annotation: Subtype: Link Rect: 327, 319, 365, 330 Annotation: Subtype: Link Rect: 59, 262, 96, 272 Annotation: Subtype: Link Rect: 380, 238, 417, 249 Annotation: Subtype: Link Rect: 501, 227, 560, 238 Annotation: Subtype: Link Rect: 56, 215, 316, 226 Annotation: Subtype: Link Rect: 218, 192, 256, 203 Annotation: Subtype: Link Rect: 400, 169, 437, 180 Annotation: Subtype: Link Rect: 59, 147, 96, 157 Annotation: Subtype: Link Rect: 122, 124, 159, 134 Annotation: Subtype: Link Rect: 165, 124, 201, 134 Annotation: Subtype: Link Rect: 86, 101, 123, 111 Annotation: Subtype: Link Rect: 497, 66, 535, 77 Page: Sequence: 16 Annotations: Annotation: Subtype: Link Rect: 127, 722, 164, 733 Annotation: Subtype: Link Rect: 244, 652, 281, 664 Annotation: Subtype: Link Rect: 167, 584, 204, 594 Annotation: Subtype: Link Rect: 149, 561, 186, 571 Annotation: Subtype: Link Rect: 259, 537, 296, 548 Annotation: Subtype: Link Rect: 520, 503, 557, 514 Annotation: Subtype: Link Rect: 264, 457, 301, 468 Annotation: Subtype: Link Rect: 416, 411, 454, 422 Checksum: a5006af7 Type: CRC32 Checksum: 37b28e62f06141dee1e2e29dcfb99aba Type: MD5 Checksum: e4bc4531ac9f262f111f65958e7c2ab32fb7b444 Type: SHA-1 Checksum: 73e9f4d378c2d9fbafd16156745a5c8eb0c5793b099067d020e0273f41aebdb9 Type: SHA-256